Base Case A song about recursion
Sing it back
Can you finish the lyrics?
Eight quick questions on “Base Case”. No music, just your memory. Then share your score and challenge a friend.
Recursion in one paragraph
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, which returns an answer directly without another call, and a recursive case, which moves the input closer to that base case. Each call gets its own frame on the call stack; when the base case is reached, the calls return one by one and their frames are popped off. If the base case is missing or never reached, the calls keep piling up and the program usually crashes with a stack overflow. Classic examples are factorial, walking through trees, and divide-and-conquer algorithms such as merge sort.
Key facts from the song
- A recursive function calls itself on a smaller version of the same problem.
- The base case returns an answer directly and stops the recursion; the recursive case moves the input closer to the base case.
- Each call gets its own frame on the call stack, and the frames are popped off as the calls return.
- With no reachable base case, calls pile up until the call stack runs out of space: a stack overflow.
- Factorial is the classic example: n factorial is n times (n − 1) factorial, with 0! = 1 as the base case.
Where it fits in your course
- US level
- College (undergraduate)
Lyrics
Verse 1
Recursion is a function calling itself to get it done
Hand a smaller copy of the problem down to the next one
The base case is the stopping point, it answers straight away
The recursive case moves closer, shrinking problems on the way
Chorus
Base case, base case, gotta know when to stop
Every call pushes a frame on the call stack, piled on top
Hit the base case, then return, and the frames unwind in turn
Lose the base case, stack overflow, that’s the lesson that you learn
Verse 2
Take factorial of n: it’s n times factorial of n minus one
Down to zero factorial, that’s one, and the base case says it’s done
Divide and conquer: merge sort splits the list, sorts each half, merges back
Trees are made of smaller trees, so recursion stays on track
Chorus
Base case, base case, gotta know when to stop
Every call pushes a frame on the call stack, piled on top
Hit the base case, then return, and the frames unwind in turn
Lose the base case, stack overflow, that’s the lesson that you learn
Outro
Smaller and smaller till the base case, then the answers travel back
Recursion, calling on itself, one frame upon the stack
Recursion flashcards
Say the answer out loud, then tap the card to check it. Or test yourself quick-fire.
1What is recursion?
When a function calls itself on a smaller version of the same problem.
2What is the base case?
The case the function answers directly, without calling itself again; it stops the recursion.
3What happens on the call stack during recursion?
Each call pushes a new frame; when the base case is reached, the calls return and the frames are popped off in turn.
4What is the recursive definition of factorial?
n! = n × (n − 1)!, with the base case 0! = 1.
Questions about recursion
Still wondering about something? Ask us and we’ll reply within two working days.
What is recursion in programming?
Recursion is when a function calls itself to solve a smaller version of the same problem, and keeps doing so until it reaches a case simple enough to answer directly, called the base case.
What is a base case in recursion?
The base case is the input a recursive function can answer directly, without calling itself again. It is what stops the recursion: for factorial, the base case is 0! = 1.
What causes a stack overflow in recursion?
Each recursive call adds a frame to the call stack, which has limited space. If the base case is missing or never reached, or the recursion is simply too deep, the frames keep piling up until the stack runs out of room and the program crashes.
Is recursion better than iteration?
Neither is always better. Any recursive algorithm can be rewritten with a loop and an explicit stack. Recursion is often clearer for trees and divide-and-conquer problems, but every call uses stack space, so very deep recursion can overflow where a loop would not.