Questions: Recursion and Tail-Recursion Optimization

Question 1

Which of the following is a tail-recursive factorial implementation?

• A. fact(n) = n * fact(n-1), with fact(0) = 1
• B. fact(n, acc) = fact(n-1, n*acc), with fact(0, acc) = acc
• C. fact(n) = fact(n-1) + (n - fact(n-1) + fact(n))
• D. Any function that calls itself exactly once

Answer: (B)

Option B is tail-recursive because the recursive call `fact(n-1, n*acc)` is the absolute last operation — the function simply returns whatever the recursive call returns, with no further computation. Option A is NOT tail-recursive: after `fact(n-1)` returns, the function still needs to multiply by `n`. That pending multiplication means the current stack frame must be kept alive, preventing optimization. The key test is: 'Is there any computation that uses the return value of the recursive call?' If yes, it's not tail-recursive.

Question 2

What does tail-call optimization (TCO) allow a compiler or runtime to do?

• A. Run recursive calls in parallel threads, speeding up execution
• B. Reuse the current stack frame for the tail call, keeping stack usage constant
• C. Automatically convert any recursive function into an iterative loop
• D. Detect infinite recursion at compile time and report an error

Answer: (B)

When the recursive call is the last operation, the current frame is no longer needed — there is nothing to return to. TCO exploits this by replacing ('overwriting') the current frame with the new call rather than pushing a new one. This means the recursion depth has no effect on stack space: a tail-recursive function counting to a million uses the same stack space as counting to 10. Option C is wrong because TCO only applies to tail-recursive calls — arbitrary recursive functions still require growing stacks.

Question 3

A function is tail-recursive if and mainly if the recursive call is the last syntactic line in the function body.

• T. True
• F. False

Answer: False

Being the last line is not the same as being the last operation. Consider `return n * factorial(n-1)` — the recursive call is on the last line, but the multiplication by n happens after it returns. The correct criterion is that no computation uses the return value of the recursive call — i.e., the function simply returns whatever the recursive call returns, with no pending work. Tail recursion is about the call being in tail position, not its syntactic location.

Question 4

Most programming languages that support recursion will apply tail-call optimization to tail-recursive functions.

• T. True
• F. False

Answer: False

TCO is a language/runtime design choice, not a universal guarantee. Scheme and many functional languages (Haskell, Erlang, Elixir) mandate TCO. Python and Java do not implement it — a tail-recursive function in Python will still grow the stack and hit the recursion limit just like any other recursive function. This has practical consequences: code written in a tail-recursive style for a TCO language must be manually converted to use an explicit loop or accumulator when ported to a language without TCO.

Question 5

Explain why a tail-recursive function can execute in constant stack space, while a non-tail-recursive function requires stack space proportional to the recursion depth.

Model answer: Each recursive call normally pushes a new stack frame to record local variables and the return address — where to continue when the call returns. In non-tail recursion, the caller has pending work (like multiplying by n) after the recursive call returns, so its frame must stay on the stack. In tail recursion, the recursive call is the last action: the caller will simply pass the result up unchanged, so its frame is immediately disposable. A compiler implementing TCO recognizes this and reuses (overwrites) the current frame for the tail call rather than pushing a new one, keeping the stack depth constant at 1 frame regardless of how many 'recursive' steps execute.

This is why tail recursion is essentially iteration in disguise: the reused frame acts exactly like updating loop variables in-place. The transformation from tail-recursive style to explicit loop is always mechanical: the accumulator parameter becomes the loop variable, the base case becomes the loop exit condition, and the recursive call becomes updating the variable and looping again.