Recursion solves a problem by having a function call itself on smaller instances of the same problem. A useful recursive design separates a base case, which stops, from a recursive case, which reduces the problem. Without a base case, execution becomes infinite recursion, much like an infinite loop. section 1.1
Fibonacci: from direct translation to practical code
The Fibonacci rule is fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1. In Swift, fib2 checks n < 2 before making its two recursive calls. This version works for small values, but repeats the same calls so often that fib(50) will not finish promptly. Memoization stores completed results in a dictionary, while an iterative version avoids recursive calls altogether. section 1.1
Apply the technique with these practical checks:
- Identify the smallest valid input and return its answer directly. section 1.1
- Make every recursive call move toward that base case; otherwise, the function may never terminate. section 1.1
- Remember that an iterative solution can replace any recursive technique when that implementation is clearer or more practical. section 1.6
Towers of Hanoi
With stacks representing towers, moving one disc is the base case. Moving more than one disc means recursively moving the upper discs to a temporary tower, moving the largest disc, and recursively moving the upper discs onto the destination tower. The Swift hanoi function expresses these three moves directly. section 1.5
