Skip to main content
All answers

Computer Science · Sample answer

How does recursion work, and how do you trace a recursive function?

This is a sample explanation showing the kind of help tutors give. It is not an answer from a specific tutor.

The explanation

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs two parts:

  • Base case: a simple input it can answer straight away, without calling itself. This is what stops the recursion.
  • Recursive case: it calls itself on a smaller input and uses that answer to build its own.

Example: factorial. 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! = 4 × 3!, so factorial can be defined in terms of a smaller factorial:

  • If n is 0, return 1. (base case)
  • Otherwise, return n × factorial(n − 1). (recursive case)

Tracing factorial(4). Each call has to wait for the call below it to finish. Going down:

  1. factorial(4) needs factorial(3)
  2. factorial(3) needs factorial(2)
  3. factorial(2) needs factorial(1)
  4. factorial(1) needs factorial(0)
  5. factorial(0) hits the base case and returns 1

Then the answers return back up, each one finishing its multiplication:

  • factorial(1) = 1 × 1 = 1
  • factorial(2) = 2 × 1 = 2
  • factorial(3) = 3 × 2 = 6
  • factorial(4) = 4 × 6 = 24

The call stack: each waiting call is stored on the call stack, with its own copy of n. That is why the calls pile up going down and are resolved in reverse order going back up. If there is no base case, or the input never reaches it, the stack keeps growing until the program crashes with a stack overflow.

A tip for tracing on paper: draw each call as a box indented under the one that called it, write what it is waiting for, and fill in the returned value when you come back up. Tree-shaped recursion, such as a Fibonacci function that calls itself twice, is easiest to trace as an actual tree.

How to write your own recursive function:

  1. Find the smallest input you can answer directly. That is your base case.
  2. Assume the function already works for a smaller input (n − 1, half the list, the rest of a string).
  3. Write how to build the answer for n from that smaller answer.
  4. Check that every recursive call moves closer to the base case.

Common mistakes:

  • Forgetting to return the recursive result, so the answer is lost on the way back up.
  • A base case that some inputs skip past, such as checking n == 0 when n can be negative or decreases by 2.

Up against a deadline? Next time you're stuck on computer science homework and short on time, post it on HomeworkHero with your deadline. There's no posting fee, you compare offers from tutors and choose who to work with, and your payment is held in escrow until you approve the work.

Topics

  • recursion
  • call stack
  • base case
  • programming
  • computer science

Get help that fits your question.

Post your question with no posting fee, compare offers from tutors who know the subject, and choose who to work with.