Skip to main content

Trace Recursion and Sorting by Hand

Retrieval Prompts​

  1. What two pieces does every recursive function need?
  2. What is the call stack doing while recursion runs?
  3. How does selection sort decide what to do next?
  4. What job does the pivot perform in quicksort?
  5. Why is quicksort often discussed as divide-and-conquer?

Compare and Distinguish​

Compare these:

  • selection sort vs quicksort
  • loop-based repetition vs recursive self-calls
  • a base case vs a recursive case
  • repeated scanning vs partitioning

Focus on structure, not syntax.

Common Mistake Check​

If your recursive step does not move toward a smaller problem, it is probably broken. If your selection sort trace never shows a full scan for the next smallest item, it is incomplete. If your quicksort explanation never mentions partitioning around a pivot, you are skipping the key idea.

Mini Application​

Do both parts:

  1. Hand-trace factorial(4) or a recursive sum on [8, 3, 6, 2] and draw the call stack states.
  2. On [8, 3, 6, 2, 5], show:
    • the first two passes of selection sort
    • one quicksort partition using the first element as pivot

For your work, label:

  • base case
  • recursive case
  • intermediate states
  • what work is waiting on the stack
  • final result or partial sorted state

If you know a programming language already, optionally implement the example and add one assertion for the final answer.

Evidence Check​

You are done only when:

  • the stopping condition is written explicitly
  • each recursive step clearly shrinks the problem
  • you can explain where the stack grows and where it unwinds
  • your selection sort trace shows repeated scanning for the next smallest item
  • your quicksort trace shows partitioned sub-arrays before the final sorted result