Questions: Recursion Basics

Question 1

What happens when a recursive function is called without a valid base case?

• A. The function returns None automatically
• B. The function runs once and exits
• C. The call stack grows without bound until the program crashes with a stack overflow
• D. The compiler detects the infinite loop and refuses to run the code

Answer: (C)

Without a base case, each call to the function spawns another call, which spawns another — the call stack accumulates frames indefinitely. Most environments impose a stack size limit, and when it is exceeded, the program crashes with a stack overflow error (or RecursionError in Python). The function does not self-terminate, and most languages do not statically detect this at compile time.

Question 2

A recursive solution to a problem is generally faster and uses less memory than an equivalent iterative solution.

• T. True
• F. False

Answer: False

This is a common misconception. Each recursive call creates a new stack frame with its own local variables, consuming memory proportional to the call depth. An iterative loop reuses the same memory. For deep recursions (e.g., large n in factorial), this overhead is substantial. Some algorithms (like tree traversals) are more naturally expressed recursively, but efficiency claims require analysis — recursion is not inherently better.

Question 3

Explain what the call stack is doing during a recursive computation, and why each call needs its own stack frame.

Model answer: The call stack tracks the state of each active function call. Each recursive call gets its own stack frame containing its local variables and the return address. This is necessary because each call is an independent invocation working on a different subproblem — it must remember its own state while waiting for the deeper call to return.

This is the key to understanding why recursion works at all. When factorial(5) calls factorial(4), the runtime can't forget that factorial(5) is in progress — it needs to multiply the result by 5 when factorial(4) returns. The stack frame preserves this context. Without separate frames, recursive calls would clobber each other's variables. Understanding the stack also explains why forgetting to return the recursive call's result is such a common bug: the result is computed correctly but then discarded.