Call Stack & Base Cases

Foundations

A recursive function solves a problem by calling itself on a smaller version of the same problem. Each call gets a frame on the call stack holding its own arguments, and frames leave in last-in, first-out order, just like the pushes and pops of the Stack lesson: a call that makes another call waits until it returns. A base case is an input small enough to answer directly; without one, frames pile up until the program crashes.

Writing recursion takes a leap of faith: assume the call on the smaller input already returns the right answer, and decide only how to finish the current call with it. Then check that every chain of smaller calls reaches a base case. Each frame does a little work on the way down, to set up its smaller call, and a little on the way back, to combine.

Sum nums = [7, 1, 5, 3, 6] recursively: total(nums) returns nums[0] + total(nums[1:]), and the base case total([]) returns 0. The calls stack six frames deep, from total([7, 1, 5, 3, 6]) down to total([]); then the answers return upward: 0, 6, 9, 14, 15, and finally 22.

• Stack

  Each call waits on the call stack until the calls it made return. That lesson covers push and pop.

  Open lesson

Case Scenario

K-th Symbol in Grammar builds rows from "0": each row replaces every 0 with 01 and every 1 with 10, and the question asks for position k of row n. That position was written by position (k + 1) // 2 of the row above, a smaller call, and row 1 is the base case. For n = 4 and k = 5, the chain climbs through rows 3, 2, and 1 and returns 1.

The direct approach builds every row from "0" up to row n, then reads position k. Each row is twice as long as the one before, so row n holds 2ⁿ⁻¹ symbols: 8 here, but over 500 million by row 30, all built to read a single position.

The Pattern

The invariant: kthGrammar(n, k) returns the right symbol for every smaller row, so each call trusts its parent's answer and only copies it, for odd k, or flips it, for even k. Every chain of calls drops one row and ends at row 1, the base case.

Check it against the walkthrough. Position 5 of row 4 came from position (5 + 1) // 2 = 3 of row 3, which came from 2 in row 2, then 1 in row 1, the base case, 0. Returning, row 2's even position flipped 0 to 1, and rows 3 and 4, both odd positions, copied it: 1.

Four frames waited on the stack, one per row, and no row was ever built. That shape, one smaller call plus a stopping condition, is all recursion needs. Choosing the smaller call, and trusting its answer, is the whole design.

Complexity

There is one call per row, each with O(1) work, so time is O(n). The calls wait on the stack until row 1 answers, so space is O(n). Building the rows costs O(2ⁿ) time and memory: row 30 alone has over 500 million symbols.