🎓 Prepared by students from Boğaziçi University

What is Recursion?

Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that stops the calls and a recursive case that moves toward it.

Short answer

Recursion is when a function calls itself to break a problem into smaller identical subproblems until it reaches a base case that can be answered directly, then the results combine back up.

Call stack for factorial(4)

1
factorial(4)
calls factorial(3), waits for its result
↓
2
factorial(3)
calls factorial(2), waits for its result
↓
3
factorial(2)
calls factorial(1), waits for its result
↓
4
factorial(1)
calls factorial(0), waits for its result
↓
5
factorial(0) — base case
returns 1 directly, no more calls
↓
6
Unwind
1×1=1, 2×1=2, 3×2=6, 4×6=24 → final answer 24

Step-by-step worked examples

Compute factorial(5) recursively.

factorial(5) = 5 × factorial(4)
factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1 × factorial(0) = 1 × 1 = 1
Unwind: 2×1=2, 3×2=6, 4×6=24, 5×24=120
factorial(5) = 120

Sum the list [3, 5, 2] using recursion.

sum([3,5,2]) = 3 + sum([5,2])
sum([5,2]) = 5 + sum([2])
sum([2]) = 2 + sum([]) = 2 + 0 = 2
Unwind: 5+2=7, 3+7=10
Result: 10

Find Fibonacci(5) using the recursive definition F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1.

F(2) = F(1)+F(0) = 1+0 = 1
F(3) = F(2)+F(1) = 1+1 = 2
F(4) = F(3)+F(2) = 2+1 = 3
F(5) = F(4)+F(3) = 3+2 = 5
Result: F(5) = 5

Flashcards

Quick quiz

Q1.What is the base case in a recursive function?

Correct answer: B. The base case is the simplest input that can be answered directly without another recursive call, stopping the chain.

Q2.What happens if a recursive function has no base case?

Correct answer: B. Without a base case the function never stops calling itself, exhausting the call stack.

Q3.In factorial(4) = 4 × factorial(3), what is factorial(3) called?

Correct answer: B. factorial(3) is the recursive call — the function invoking itself on a smaller input.

Q4.What is F(4) if F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1?

Correct answer: B. F(2)=1, F(3)=2, F(4)=F(3)+F(2)=2+1=3.

📄Download this topic as a printable worksheet (PDF)Summary + 10 questions + answer key — print it, share it in class.↓

Study better with Bounlu apps

Notek

The full card deck, worked steps and AI-tutor support for “What is Recursion?” are in Notek — study by hand before your exam.

Get it free

PromyNever miss an exam or homework deadline with Promy: AI turns the dates in your inbox into reminders automatically.

Common mistakes

✗

Forgetting to write a base case. — Correct: Always define a base case first — it's what actually stops the recursion from running forever.

✗

Believing the recursive case doesn't need to move toward the base case. — Correct: Each recursive call must shrink the problem (e.g., n-1) so it eventually reaches the base case.

✗

Thinking recursion is always faster than a loop. — Correct: Recursion often uses more memory (call stack) and can be slower than an equivalent iterative loop.

✗

Assuming recursive calls happen 'in parallel'. — Correct: Recursive calls happen sequentially — each call waits (pauses) until its own recursive call returns.

FAQ

What is recursion?

Recursion is when a function calls itself with a smaller version of the same problem until reaching a base case.

What is the formula for recursion?

There's no single formula, but the pattern is always: base case (direct answer) + recursive case (call itself on smaller input), e.g., n! = n × (n−1)! with 0! = 1.

What are examples of recursion?

Factorial, Fibonacci numbers, summing a list, tree traversal, and the recursive binary search algorithm.

How do you calculate a recursive function by hand?

Expand each call until you hit the base case, get its direct value, then 'unwind' back up multiplying/adding the results at each level.