Recursion study song
Quick answer
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem. Every correct recursive function needs a base case that stops the calls and a recursive case that moves toward it.
Exam questions ask you to trace calls for factorial or Fibonacci, find the missing base case in a buggy function, and state the time complexity of naive recursion. The mental picture is a call stack that grows on the way down and unwinds on the way back up. A song with a verse that keeps returning to the opening line, then a final line that ends the loop, mirrors that structure and makes the base case hard to forget.
5 facts to know about recursion
- 1Every recursive function needs a base case; without one the calls never stop and a stack overflow occurs.
- 2Factorial is defined as n! = n × (n − 1)! with the base case 0! = 1.
- 3Naive recursive Fibonacci runs in O(2^n) time because it recomputes the same subproblems.
- 4Memoization stores earlier results and reduces recursive Fibonacci to O(n) time.
- 5Each recursive call adds a frame to the call stack, so recursion depth n uses O(n) stack space.














