Chapter 22 Exercises: Recursion — The Power and Peril of Self-Reference

Part A: Conceptual Understanding

A.1. Define recursion in your own words. What are the two essential components of every correct recursive solution? Why is each one necessary?

Guidance Recursion is a problem-solving technique where a function solves a problem by calling itself with a simpler version of the problem. The two essential components are: (1) a base case — a condition under which the function returns directly without recursing, which prevents infinite recursion; and (2) a recursive case — a self-call with arguments that move closer to the base case, which ensures progress toward termination.

A.2. Trace the execution of Factorial(5) by drawing all five stack frames. For each frame, show the value of N and the return value once the frame unwinds.

Guidance Frame 5 (top): N=0, returns 1. Frame 4: N=1, returns 1*1=1. Frame 3: N=2, returns 2*1=2. Frame 2: N=3, returns 3*2=6. Frame 1 (bottom): N=4, returns 4*6=24. The final result from Factorial(5) itself is 5*24=120 (this is the original call's frame). Maximum stack depth is 6 frames (including the call for N=5).

A.3. Explain the difference between the "winding" and "unwinding" phases of recursion. In Countdown(5), during which phase are the numbers printed? What about in CountUp(5)?

Guidance The winding phase is when recursive calls are being made, pushing frames onto the stack. The unwinding phase is when base cases return and deferred computations are evaluated. In Countdown(5), numbers are printed during winding (before the recursive call). In CountUp(5), numbers are printed during unwinding (after the recursive call returns).

A.4. Why does the naive recursive Fibonacci function have exponential time complexity? Draw the call tree for Fibonacci(6) and count the total number of function calls.

Guidance Each call to Fibonacci(n) for n>1 spawns two recursive calls, creating a binary tree of calls. Many sub-problems are computed multiple times: Fibonacci(4) is computed twice, Fibonacci(3) three times, etc. For Fibonacci(6), the total number of calls is 25. The time complexity is O(2^n) because the call tree roughly doubles in size for each increment of n.

A.5. What is a stack overflow, and why are recursive functions particularly susceptible to causing one? How can you estimate whether a recursive function will overflow the stack?

Guidance A stack overflow occurs when the call stack exceeds its allocated memory. Recursive functions are susceptible because each call adds a frame. To estimate: stack size / frame size = max depth. With a 1 MB stack and ~100-byte frames, maximum depth is about 10,000 calls. If your recursion depth exceeds this, consider iteration.

A.6. Explain the difference between direct recursion and indirect (mutual) recursion. Why do you need forward declarations for mutual recursion in Pascal?

Guidance Direct recursion: function A calls itself. Indirect/mutual recursion: function A calls function B, which calls A again. In Pascal, identifiers must be declared before use. With mutual recursion, A references B and B references A — a chicken-and-egg problem. The forward keyword declares A's signature before B's body, allowing B to call A.

A.7. What is tail recursion? Rewrite the following non-tail-recursive function as a tail-recursive one:

function Sum(N: Integer): Integer;
begin
  if N = 0 then Sum := 0
  else Sum := N + Sum(N - 1);
end;
Guidance Tail recursion means the recursive call is the very last operation. The given function is not tail-recursive because it adds N to the result of Sum(N-1) after the call returns. Tail-recursive version: 
function SumTail(N: Integer; Acc: Integer): Integer;
begin
  if N = 0 then SumTail := Acc
  else SumTail := SumTail(N - 1, Acc + N);
end;
// Call as SumTail(10, 0)

A.8. The chapter states that "recursion works because the problem has self-similar structure." Give three real-world examples (not from programming) of self-similar structures.

Guidance Examples: (1) A tree branch — each branch has smaller branches that look like miniature versions of the tree. (2) A coastline — zooming in reveals smaller bays and peninsulas that resemble the larger coastline shape. (3) An organizational chart — each department has sub-departments with managers, mirroring the structure of the organization as a whole. (4) Russian nesting dolls. (5) A book's table of contents — sections contain subsections which contain sub-subsections.

Part B: Applied Analysis

B.1. For each of the following problems, determine whether recursion or iteration is the better approach. Justify your answer.

(a) Computing the sum of integers from 1 to N. (b) Traversing a binary tree in post-order. (c) Processing every line of a 10-million-line text file. (d) Generating all permutations of a string. (e) Searching a sorted array for a target value.

Guidance (a) Iteration — linear recursion with a simple loop equivalent. (b) Recursion — tree structure is naturally recursive; iterative post-order is complex. (c) Iteration — recursion depth of 10 million would overflow the stack. (d) Recursion — permutation generation is naturally recursive (choose one element, permute the rest). (e) Either works well — binary search is elegant both recursively and iteratively; the recursion depth is O(log n) so stack overflow is not a concern.

B.2. Consider a function that computes the Greatest Common Divisor using Euclid's algorithm:

function GCD(A, B: Integer): Integer;
begin
  if B = 0 then GCD := A
  else GCD := GCD(B, A mod B);
end;

(a) Trace GCD(48, 18) step by step. (b) What is the base case? What is the recursive case? (c) Is this tail recursive? Explain. (d) Write an iterative version.

Guidance (a) GCD(48,18) → GCD(18,12) → GCD(12,6) → GCD(6,0) → 6. (b) Base: B=0, return A. Recursive: GCD(B, A mod B). (c) Yes — the recursive call is the last operation; nothing is done with the result. (d) Use a while loop: while B<>0 do begin Temp:=B; B:=A mod B; A:=Temp; end; GCD:=A.

B.3. Write a recursive function ReverseString(S: string): string that reverses a string without using a loop. What is the base case? What is the time complexity?

Guidance Base case: empty string or single character returns itself. Recursive case: last character + ReverseString(all but last). Time complexity: O(n^2) because each recursive call creates a new string via concatenation, which is O(n). An iterative version using index swapping is O(n).

B.4. Rosa wants PennyWise to find the total spending for a category and all of its subcategories. Given the following category tree:

All Expenses
├── Food ($0 direct)
│   ├── Groceries ($412)
│   ├── Restaurants ($0 direct)
│   │   ├── Fast Food ($87)
│   │   └── Fine Dining ($211)
│   └── Coffee ($113)
└── Transport ($50 direct)
    ├── Gas ($280)
    └── Bus ($95)

Trace the execution of CalculateCategoryTotal(Food) from the PennyWise checkpoint. Show every recursive call and the returned value.

Guidance CalculateCategoryTotal(Food): Total starts at $0 (Food's direct amount). Recurse on Groceries: returns $412 (leaf node). Recurse on Restaurants: starts at $0 direct, recurses on Fast Food ($87) and Fine Dining ($211), returns $0+$87+$211=$298. Recurse on Coffee: returns $113 (leaf). Final: $0+$412+$298+$113 = $823.

Part C: Code Exercises

C.1. Write a recursive function SumDigits(N: Integer): Integer that returns the sum of the digits of a non-negative integer. Example: SumDigits(12345) returns 15.

Hint Base case: N < 10, return N. Recursive case: (N mod 10) + SumDigits(N div 10).

C.2. Write a recursive function IsPalindrome(S: string): Boolean that returns True if a string reads the same forwards and backwards. Ignore case. Examples: IsPalindrome('racecar') returns True; IsPalindrome('hello') returns False.

Hint Base case: string of length 0 or 1 is a palindrome. Recursive case: first char = last char AND the middle substring is a palindrome. Use UpCase for case-insensitive comparison.

C.3. Write a recursive procedure PrintBinary(N: Integer) that prints the binary representation of a non-negative integer. Example: PrintBinary(13) prints 1101.

Hint Base case: N = 0, do nothing (or handle N=0 specially to print '0'). Recursive case: PrintBinary(N div 2) first, then Write(N mod 2). The recursion prints higher-order bits first because they are printed during unwinding.

C.4. Write a recursive function Power(Base: Real; Exp: Integer): Real that computes Base^Exp using the fast exponentiation algorithm (repeated squaring). Test it with Power(2, 10) = 1024 and Power(3, 0) = 1.

Hint Base cases: Exp=0 returns 1. If Exp is even, compute Half := Power(Base, Exp div 2) and return Half*Half. If Exp is odd, return Base * Power(Base, Exp - 1). Handle negative exponents by returning 1/Power(Base, -Exp).

C.5. Write a recursive procedure DrawTriangle(N: Integer) that prints a right triangle of asterisks. DrawTriangle(4) should output:

*
**
***
****
Hint Base case: N <= 0, do nothing. Recursive case: DrawTriangle(N-1) first (recursion before printing gives ascending order), then print a line of N asterisks.

C.6. Write a recursive function ListMax(Node: PNode): Integer that returns the maximum value in a linked list of integers. Assume the list is non-empty.

Hint Base case: Node^.Next = nil, return Node^.Data. Recursive case: return the larger of Node^.Data and ListMax(Node^.Next). Use a local variable to store the recursive result, then compare.

C.7. Write a recursive function CountNodes(Node: PTreeNode): Integer that counts the total number of nodes in a binary tree.

Hint Base case: Node = nil, return 0. Recursive case: 1 + CountNodes(Node^.Left) + CountNodes(Node^.Right).

C.8. Write a recursive function TreeHeight(Node: PTreeNode): Integer that returns the height of a binary tree (the longest path from root to leaf). An empty tree has height 0; a single node has height 1.

Hint Base case: Node = nil, return 0. Recursive case: 1 + Max(TreeHeight(Left), TreeHeight(Right)). You will need to write or use a Max function for integers.

C.9. Write a recursive function Flatten(Node: PCategoryNode): string that produces a comma-separated list of all category names in the PennyWise category tree. For the sample tree in Section 22.9, the output should be something like: All Expenses, Food, Groceries, Restaurants, Fast Food, Fine Dining, Coffee, Transport, Gas, Public Transit, Rideshare, Entertainment, Utilities, Electric, Water, Internet.

Hint This is a pre-order traversal of the N-ary tree. Base case: Node = nil, return empty string. Recursive case: start with Node^.Name, then concatenate the results of Flatten on each child, inserting commas appropriately.

C.10. Implement the Tower of Hanoi solution as a recursive procedure Hanoi(N: Integer; Source, Target, Auxiliary: Char). Test with N = 3 and verify that it produces the correct 7 moves.

Hint Base case: N = 0, do nothing. Recursive case: (1) Move N-1 disks from Source to Auxiliary using Target as helper. (2) Move disk N from Source to Target (print this move). (3) Move N-1 disks from Auxiliary to Target using Source as helper. Total moves = 2^N - 1.

Part D: Challenge Exercises

D.1. Recursive Flood Fill. Write a recursive procedure that performs flood fill on a 2D character grid. Given a starting position (row, col), a target character, and a replacement character, replace all connected cells containing the target character. This is the algorithm behind the "paint bucket" tool in image editors.

Hint Base cases: position out of bounds, or cell does not contain target character, or cell already contains replacement. Recursive case: replace current cell, then recurse on the four neighbors (up, down, left, right). Be careful about the order of checks to avoid infinite recursion.

D.2. Recursive Directory Listing. Write a program that recursively lists all files in a directory and its subdirectories, with indentation showing the nesting level. Use Free Pascal's SysUtils unit (FindFirst, FindNext, FindClose) or the FileUtil unit.

Hint Use FindFirst/FindNext to iterate over entries in a directory. For each entry, if it is a directory (and not '.' or '..'), recurse into it with increased indentation. If it is a file, print it with the current indentation.

D.3. Recursive Merge Sort. Implement merge sort on an array of integers using recursion. (This is a preview of Chapter 23, but try it now using only the recursive thinking from this chapter.)

Hint Base case: array of length 0 or 1 is already sorted. Recursive case: split the array in half, sort each half recursively, then merge the two sorted halves. The merge step walks through both halves simultaneously, always picking the smaller element.

D.4. Mutual Recursion: Even/Odd Classifier. Extend the IsEven/IsOdd mutual recursion example to handle negative numbers. Then rewrite it without mutual recursion and compare the two approaches.

Hint For negative numbers, convert to positive first: IsEven(Abs(N)). Without mutual recursion, a simple N mod 2 = 0 check suffices. The exercise illustrates that mutual recursion, while instructive, is not always the best tool.

D.5. Recursive Expression Evaluator. Build on the expression parser sketch from Section 22.7. Implement a complete calculator that reads a string like "3 + 4 * (5 - 2)" and evaluates it to 15, respecting operator precedence and parentheses using mutual recursion.

Hint You need three mutually recursive functions: ParseExpression (handles +/-), ParseTerm (handles *//), and ParseFactor (handles numbers and parenthesized expressions). Use a global index variable to track the current position in the input string. Handle whitespace by skipping spaces.

D.6. Recursive Backtracking: N-Queens. Write a recursive program that places N queens on an N×N chessboard such that no two queens threaten each other. Print all solutions for N = 8.

Hint Place queens one column at a time. For each column, try every row. If the placement is safe (no queen in the same row, and no queen on the same diagonal), place the queen and recurse on the next column. If the recursion fails (no valid row for the next column), backtrack by removing the queen and trying the next row.

D.7. Performance Comparison. Write a program that times both the recursive and iterative versions of Fibonacci for N = 10, 20, 30, 35, 40. Create a table showing the execution time for each. At what value of N does the recursive version become impractically slow?

Hint Use GetTickCount64 from SysUtils or Now from DateUtils for timing. The recursive version becomes noticeably slow around N=35 and impractical around N=45. The iterative version remains near-instantaneous for all values.

D.8. PennyWise Category Tree Builder. Extend the PennyWise category tree from Section 22.9 with these recursive operations: (a) DeleteCategory — removes a category and reassigns its children to the parent. (b) MoveCategory — moves a category subtree from one parent to another. (c) MergeCategories — combines two categories, summing their amounts and concatenating their children.

Hint DeleteCategory: find the node, copy its children to its parent's children array, then dispose of the node. MoveCategory: find and detach the subtree from its current parent, then attach it to the new parent. MergeCategories: find both nodes, combine their child arrays, sum their amounts, remove the second node. All operations require recursive search to find nodes by name.

Part M: Interleaving Review (Spaced Practice)

These exercises revisit concepts from earlier chapters, interleaved with recursion.

M.1. (From Ch 7/8) Explain why each recursive call to Factorial(N) gets its own copy of N. What mechanism of the Pascal runtime makes this possible?

Guidance Value parameters in Pascal are copies. Each call to Factorial creates a new stack frame with its own copy of N. The call stack mechanism (Chapter 8) ensures that each invocation's local variables are independent. This is why Factorial(3)'s N=3 is not affected when Factorial(2) sets N=2 in its own frame.

M.2. (From Ch 14/15) Write a recursive function that creates a copy of a linked list (a new list with the same data but different nodes). How does your use of New in the recursive function interact with the call stack?

Guidance Each recursive call allocates a new node on the heap with New. The heap allocations persist after the recursive calls return. The call stack is temporary (frames are popped), but the heap nodes remain, forming the new list.

M.3. (From Ch 16/17) How would you implement a recursive ToString method in a class hierarchy? Consider a TExpression class with subclasses TNumber, TBinaryOp, and TParenExpr. Each class's ToString calls ToString on its children — is this recursion, polymorphism, or both?

Guidance It is both. The recursive structure comes from the expression tree (a binary operation contains sub-expressions). The polymorphism comes from virtual method dispatch: each subclass implements ToString differently. This is a powerful combination common in compilers and interpreters.

M.4. (From Ch 9) Convert the recursive RecursiveSum function from Section 22.3 to use a for loop. Which version do you find more readable? Which is more efficient?

Guidance Iterative: a simple for loop accumulating elements. The iterative version is more efficient (no function call overhead) and arguably equally readable for this simple case. The recursive version mirrors the mathematical definition more closely but offers no practical advantage for array summation.