Recursive calls, stack frames and induction

By UK A Level Computer Science · independent study · myAudience

Original conceptual plate generated with OpenAI imagegen; inspected in scratch production. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Recursive calls, stack frames and induction

Recursion occurs when a computation calls itself on a related problem. A base case supplies a result without another recursive call; a recursive case reduces the problem and combines the smaller result. The triangular-number function is defined on nonnegative integers by T(0)=0 and T(n)=n+T(n−1) for n>0. This is a mathematical definition, while a Python implementation is a physical computation with finite memory and a recursion-depth limit. The distinction matters: a mathematically well-defined result can still be unavailable through this particular implementation for a very large input.

A conceptual stack frame stores the call's parameters, local information and a return location. At the deepest point of triangular(3), four calls are active with n values 3,2,1,0. Each call has its own binding of n. The waiting call for n=3 does not become n=2 when it invokes the next call. It must remember to add its own 3 after the smaller computation returns. The return location means where execution resumes; it is not the same thing as the result value returned.

The selected recursion plate places the most recent call T(0) at the top and the first call T(3) at the bottom. Read the left call sequence as argument values 3,2,1,0. Read the right return sequence in its numbered order: 0, then 1, then 3, then 6. These are conceptual frames rather than literal memory addresses. The first artwork version used upward arrows beside a top-to-bottom list of return values; that version was rejected. The corrected plate uses explicit return-order labels so the direction cannot contradict the frame ordering.

For termination, n decreases by one on the recursive branch and cannot decrease forever while remaining a nonnegative integer. The domain check is essential: a negative starting n with only n==0 as the base case would move farther from zero. For correctness, use induction. The base result is the empty sum. Assuming triangular(n−1) correctly sums 1 through n−1, adding n produces the sum through n. This proves correctness for all domain values in the abstract recurrence, while the runtime-depth qualification remains a separate implementation limit.

There are n+1 calls and n additions for input n. Under unit-cost integer arithmetic, time is Θ(n) and auxiliary call-stack space is Θ(n). An iterative sum needs Θ(n) time but O(1) auxiliary words. Pairing the first and last terms derives T(n)=n(n+1)/2, giving a constant number of arithmetic operations. Actual arbitrary-size Python integer arithmetic is not constant time in bit length, so that comparison uses the stated unit-cost model. Recursion is a method, not an automatic performance improvement.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def triangular(n):
"""Sum 1..n recursively for nonnegative integers within runtime depth."""
if type(n) is not int:
raise TypeError('integer required')
if n < 0:
raise ValueError('n must be nonnegative')
if n == 0:
return 0
return n + triangular(n - 1)
```

Worked example: Trace triangular(3), including the suspended operations and the returning values.

T(3) suspends addition of 3 while T(2) runs; T(2) suspends addition of 2; T(1) suspends addition of 1.

T(0) returns 0. T(1) resumes and returns 1+0=1.

T(2) returns 2+1=3, then T(3) returns 3+3=6. Four conceptual frames coexist at the deepest point.

Answer: 6. The completed call removes its frame before its caller continues.

Check your understanding: 1. What is T(4)? 2. Why is “it has a base case” insufficient to prove termination? 3. Compare recursive, iterative and formula-based approaches for n=10⁶, stating arithmetic and runtime assumptions.

Answer: 1. 4+T(3)=10. 2. Every valid recursive branch must progress toward a base case; a branch that calls itself with n+1 need not reach zero. 3. Ordinary Python recursion is unsuitable because of call depth and storage. A loop takes a million additions with constant auxiliary words; n*(n+1)//2 uses a fixed number of arithmetic operations and gives 500000500000. The operands grow with input bit length, so fixed operation count does not mean bit-level constant runtime.

Why: The recursion stack is not the output sequence. A recursive call does not overwrite its caller’s parameter. An induction proof establishes the recurrence; it does not remove physical runtime limits. The halting problem later concerns arbitrary programs, not an inability to prove this specific recursion terminates.