Recursion

Context: FIT1008_MOC · defining an Algorithm in terms of itself · backbone clustering Notation, Accumulator, Auxiliary Function, vs-Iteration, and →Iteration-via-Stack

Quick Revision

• 🎯 Objective: reduce to smaller subproblems of the same kind until a base case ➔ cost via recurrence, correctness via induction.
• 📦 Core Components: base + call + convergence + combine | classified by count/route/tail | reshaped by accumulator/auxiliary function.
• ⚡ Key Constraint: $\Theta (\text{depth})$ stack frames (no Python TCO) ➔ overflow; removed by an accumulator (forward) or explicit Stack (ADT) (backward).

📝 Core

1. Recursion (Four Components)

• Core mechanism ➔ a function calls itself on strictly smaller inputs.
• Four parts ➔ base case(s) + recursive call(s) + convergence + combination.
• Cost / correctness ➔ cost = recurrence (unroll/recursion tree); correctness = structural induction; no base ⟹ RecursionError.

2. Notation (Classifying)

• Count ➔ unary / binary / $n$-ary (the branching factor of the call tree).
• Route ➔ direct vs indirect/mutual.
• Tail ➔ recursive call’s result is the result (nothing on the way back) ➔ binary ⟹ $2^n$ unless subproblems shrink fast or memoised.

3. Accumulator (Forward-Carry → Tail)

• Mechanism ➔ extra parameter carries the partial result forward, combining on the way in.
• Effect ➔ makes the recursion tail-recursive, kills recomputation (Fibonacci $\Theta ({\phi }^n)\to \Theta (n)$).
• Boundary ➔ only when result builds forward; memoisation/DP is the general alternative ($\Theta (n)$ space).

4. Auxiliary Function (Driver + Worker)

• Pattern ➔ private worker carries a converging argument the public type can’t shrink (a LinkList can’t recurse on self).
• Parameter jobs ➔ converge (current.link) | accumulate | carry context (item, lo/hi).
• or short-circuit ➔ a free second base case; plumbing hidden behind a clean public signature.

5. Recursion vs Iteration

• Equivalence ➔ loops vs self-calls are Turing-equivalent; difference = where state lives.
• Practical cap ➔ TCO-less languages ⟹ iteration needed for large $n$.
• Conversion seed ➔ the base case is the negation of the loop’s continuation guard.

6. →Iteration via Explicit Stack

• Mechanism ➔ simulate the run-time stack with an explicit Stack (ADT) — push pending work, pop in a loop.
• When ➔ general conversion when an accumulator can’t (work builds on the way back).
• Payoff ➔ same $\Theta (\text{depth})$ space but on the heap ➔ no fixed call-stack limit.

⚙️ Core Implementation

🔹 Basic vs Accumulator (factorial / Fibonacci)

non-tail vs tail-recursive forms

def factorial(n):                  # NON-tail: '* n' happens AFTER the call
    return 1 if n == 0 else n * factorial(n - 1)
 
def factorial_acc(n, result=1):    # TAIL: accumulate the product going IN
    return result if n == 0 else factorial_acc(n - 1, result * n)
 
def fib(n):                        # carry the last two values -> O(n), not Θ(φ^n)
    return fib_aux(n, 0, 1)
def fib_aux(n, fm2, fm1):
    return fm2 if n == 0 else fib_aux(n - 1, fm1, fm2 + fm1)

💡 Common Mistake: Accumulator kills recomputation regardless of TCO ➔ the time win ($\Theta ({\phi }^n)\to \Theta (n)$) is independent of the space win; the tail form maps mechanically onto a while loop.

🔹 Auxiliary Function over a LinkList

len_aux / contains_aux (driver + worker)

def __len__(self) -> int:                  # driver: seed the pointer
    return self.len_aux(self.head)
def len_aux(self, current) -> int:         # worker: recurse on Node
    return 0 if current is None else 1 + self.len_aux(current.link)
 
def __contains__(self, item) -> bool:
    return self.contains_aux(self.head, item)
def contains_aux(self, current, item) -> bool:
    if current is None: return False                                   # base 1: not found
    return current.item == item or self.contains_aux(current.link, item)  # 'or' short-circuits

💡 Common Mistake: Recurse on the Node, not self ➔ a list-minus-head isn’t a new LinkList; len_aux is still $\Theta (n)$ stack frames ⟹ a long list overflows where a loop wouldn’t.

🔹 Explicit-Stack de-recursification (power)

recursive power → power_iter

def power(x, n):                       # recursive: multiplies AFTER the call (non-tail)
    tmp = 1
    if n > 0:
        tmp = power(x, n // 2)
        tmp = tmp * tmp if n % 2 == 0 else tmp * tmp * x
    return tmp
 
def power_iter(x, n):                  # explicit stack: push converging args, pop & combine
    st = []
    while n > 0:
        st.append(n); n //= 2          # phase 1: push (mimics the descent)
    tmp = 1
    while st:                          # phase 2: pop (mimics the return path)
        tmp = tmp * tmp if st.pop() % 2 == 0 else tmp * tmp * x
    return tmp

💡 Common Mistake: LIFO order is the trick ➔ print-reverse pushes all items then pops; the explicit stack on the heap dodges Python’s ~1000-frame RecursionError.

⚖️ Core Decision Matrix

Recursion shape	Convert via	Recurrence → cost	Example
Tail / forward	accumulator → plain loop (no stack)	$T(n)=T(n-1)+\Theta (1)=\Theta (n)$	factorial, fib_aux
Non-tail, single call	one explicit stack of arguments	$T(n)=T(n/2)+\Theta (1)=\Theta (\log n)$	power, binary search
Multiple calls (balanced)	explicit stack of work items	$T(n)=2T(n/2)+\Theta (n)=\Theta (n\log n)$	Merge Sort
Multiple calls (overlapping)	accumulator or memoisation/DP	$T(n)=T(n-1)+T(n-2)+\Theta (1)=\Theta ({\phi }^n)$	naive Fibonacci

When It Flips: same time Big-O, but recursion uses $\Theta (\text{depth})$ space vs iteration's $\Theta (1)$ — TCO would erase it (Python/Java lack it). The equivalence is to general iteration; the primitive-recursive / bounded-for fragment can't express Ackermann.

📊 Exam Execution Trace

Manual Execution Trace

power_iter(2, 5) (so $2^5=32$):

Step / State	Trigger Op	st	n	tmp Payload
0 (Init)	push	[5]	2	$-$
1	push	[5,2]	1	$-$
2	push	[5,2,1]	0	1
3	pop 1 (odd)	[5,2]	$-$	$1^2\cdot 2=2$
4	pop 2 (even)	[5]	$-$	$2^2=4$
5	pop 5 (odd)	[]	$-$	$4^2\cdot 2=32$

Applied Exercise

Problem: Unroll the factorial recurrence to its closed-form cost. Derivation Proof / Hand-Calculation Walkthrough:

$$\begin{array}{rl}T(n)& =T(n-1)+\Theta (1)=T(n-2)+2\Theta (1)=\dots \\ & =T(0)+n\Theta (1)=\Theta (n)\end{array}$$

Final Extracted Output: unary recursion ⟹ a path of $n$ frames ⟹ $\Theta (n)$ time and $\Theta (n)$ stack space.

🧠 Active Recall

How do you prove a recursive algorithm correct, and how does it differ from proving a loop correct?

• Hint: Map recursion to induction, loops to invariants.

Answer

• Short answer: Structural induction — base proved directly; step assumes calls correct on smaller inputs; convergence proves termination.
• Why: Same induction ➔ a loop uses a loop invariant (init/maintenance/termination) + variant — iterative and recursive forms of the same argument.

Why can a correct recursive function still crash in Python, and what are the fixes?

• Hint: No TCO + a depth cap.

Answer

• Short answer: Python caps depth (~1000) and does no tail-call optimisation ➔ deep recursion overflows.
• Why: De-recursify ➔ convert to iteration, an explicit heap stack (no cap), or an accumulator + loop; raising the limit only delays it.

Naive Fibonacci is exponential — compare the accumulator fix and the memoisation fix.

• Hint: Forward-accumulation vs general caching.

Answer

• Short answer: Both reach $\Theta (n)$; accumulator is $\Theta (1)$ extra state, memoisation $\Theta (n)$ table.
• Why: Generality ➔ accumulation works only for forward-building results; memoisation handles any overlapping-subproblem structure.

For factorial-as-tail, power, and Tower of Hanoi — does converting to iteration need nothing, an accumulator, or an explicit stack?

• Hint: Match recursion shape to conversion device.

Answer

• Short answer: Tail factorial ➔ plain loop; power ➔ explicit stack of args; Tower of Hanoi ➔ explicit stack of work items.
• Why: Pending state ➔ Hanoi’s two recursive calls must remember which sub-move to resume, exactly like call frames.

Why does recursing over a LinkList need an auxiliary function, and what three jobs can its parameter do?

• Hint: The public type can’t shrink itself.

Answer

• Short answer: A driver seeds a worker recursing on the next Node (a valid smaller argument).
• Why: Parameter roles ➔ converge (current.link), accumulate a forward result, or carry context (item, lo/hi) — behind a clean public method.