Base Case A song about recursion

Subject
Computer science
Genre
Hip-hop
Level
College
Length
1:52
Tempo
90 BPM

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

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.

  1. 1What is recursion?

    When a function calls itself on a smaller version of the same problem.

  2. 2What is the base case?

    The case the function answers directly, without calling itself again; it stops the recursion.

  3. 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.

  4. 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.

Welcome to BrainBeats

Sign in or create your free account

No password needed. Pick Google, or we’ll email you a sign-in link.

Continue with Google

or

Part of BrainBeats Plus

Unlock this song

Start your free week

7 days free, then $5.99/month billed yearly. Cancel anytime.

or

Play a free song