Learning Recursion by Inventing It

The factorial of n is n * (n-1) * (n-2) * ... * 1. By definition, factorial(0) = 1.

Before coding:

1. Write factorial(4) as 4 * factorial(3). What is factorial(3) in terms of factorial(2)? Keep going until you reach a number whose factorial you already know without any multiplication.
2. What is the smallest input for which you can answer "what is factorial(n)?" without calling factorial again? This is called the base case.
3. For every other n, how do you express factorial(n) using factorial(n-1)? This is called the recursive case.

Your derivation:

• base case: factorial(...) = ...
• recursive case: factorial(n) = ...

Write a function factorial_recursive(n) that:

• returns 1 if n is 0 (the base case),
• otherwise returns n * factorial_recursive(n - 1) (the recursive case).

Example:

factorial_recursive(5)  # Output: 120
factorial_recursive(3)  # Output: 6
factorial_recursive(0)  # Output: 1
factorial_recursive(1)  # Output: 1

Before running anything: what do you think happens if you call factorial_recursive(-1)? Walk through it: does n ever hit 0?

Now try it in the cell below --- wrapped in a try/except so it doesn't crash your whole notebook. What error do you get?

In Exercise 1.3 you saw what happens without a base case. What is the role of the base case in a recursive function?

A. It makes the function run faster

B. It tells Python to use a loop instead of recursion

C. It provides the stopping condition --- the simplest case that can be answered directly without another recursive call

D. It handles invalid inputs like negative numbers

4 * 3 means "add 4 to itself 3 times": 4 + 4 + 4 = 12.

Before coding (assume both a and b are non-negative for now):

1. What is the base case --- the value of b for which a * b is obviously 0 without doing any addition?
2. For any other b, how can you write a * b in terms of a * (b - 1)?

Your derivation:

• base case: multiply(a, 0) = ...
• recursive case: multiply(a, b) = ...

Write multiply_recursive(a, b) that works for b >= 0, without using the * operator.

Example:

multiply_recursive(4, 3)   # Output: 12
multiply_recursive(5, 0)   # Output: 0

Now suppose b can be negative --- like multiply_recursive(7, -2), which should be -14.

Before coding:

1. If b is negative, how is a * b related to a * (-b) (where -b is now positive)?
2. Rather than writing new logic, can you handle the negative case by converting b to positive, calling your existing recursive logic, and then fixing the sign of the result?

Your derivation:

if b < 0: multiply_recursive(a, b) = ...

Update multiply_recursive(a, b) to handle negative b too.

Example:

multiply_recursive(4, 3)     # Output: 12
multiply_recursive(5, 0)     # Output: 0
multiply_recursive(7, -2)    # Output: -14
multiply_recursive(-3, -3)   # Output: 9

x ** n (for a positive integer n) means multiplying x by itself n times. For example, 2 ** 3 = 2 * 2 * 2 = 8.

Before coding:

1. What's the base case --- the smallest n (a positive integer) for which x ** n is just x, with no multiplication needed?
2. For any other (larger) n, how do you write x ** n using x ** (n - 1)?

Your derivation:

• base case: power(x, 1) = ...
• recursive case: power(x, n) = ...

Write power(x, n) that returns x ** n using recursion, where n is a positive integer (n >= 1).

Example:

power(2, 3)   # Output: 8
power(5, 2)   # Output: 25

power from Part 3 only handles n >= 1. Now extend it to handle n == 0 and negative n too.

Before coding:

1. What should x ** 0 be, for any non-zero x? (No recursion needed --- this becomes a new base case.)
2. If n is negative, x ** n equals 1 divided by what?

Your derivation:

• new base case: compute_power(x, 0) = ...
• negative case: compute_power(x, n) for n < 0 = 1 / compute_power(x, ...)

Write compute_power(x, n) that returns x ** n using recursion, for any integer n --- positive, negative, or zero.

Example:

compute_power(2, 3)   # Output: 8
compute_power(2, -3)  # Output: 0.125
compute_power(5, 0)   # Output: 1
compute_power(-2, 3)  # Output: -8

Your compute_power probably handles a negative n by computing the positive power first, then taking 1 / the result. There's a route that never needs that flip: make the recursion itself climb toward zero.

For negative n, notice that $x^n = x^{n+1} / x$ --- the exponent moves up by one each call, so -3 -> -2 -> -1 -> 0 reaches the same base case that positive n reaches by counting down.

Write power_climb(x, n) with one base case (n == 0) and two recursive cases: for positive n recurse on n - 1 (as before), for negative n recurse on n + 1 using the identity above.

The lesson: a recursion just needs each call to step closer to the base case --- from below works as well as from above.

Tests:

power_climb(4, -1)   # 0.25
power_climb(2, -3)   # 0.125
power_climb(2, 3)    # 8
power_climb(5, 0)    # 1

17 / 5: how many times does 5 fit into 17, and what's left over?

Before coding:

1. Subtract 5 from 17 repeatedly, counting how many subtractions you do, until what's left is less than 5. How many subtractions did it take, and what's the leftover amount?
2. Those two numbers are the quotient and the remainder. State the base case: when the dividend is already less than the divisor, what's the quotient, and what's the remainder?
3. Otherwise --- one subtraction in --- how does the answer for (dividend, divisor) relate to the answer for (dividend - divisor, divisor)?

Your derivation:

• base case (dividend < divisor): quotient = ..., remainder = ...
• recursive case: recursive_divide(dividend, divisor) in terms of recursive_divide(dividend - divisor, divisor) = ...

Write recursive_divide(dividend, divisor) that returns a tuple (quotient, remainder), using recursion. You must not use // or %. Assume dividend >= 0 and divisor > 0.

Example:

recursive_divide(17, 5)   # Output: (3, 2)
recursive_divide(20, 4)   # Output: (5, 0)
recursive_divide(7, 3)    # Output: (2, 1)
recursive_divide(0, 1)    # Output: (0, 0)

The HCF (Highest Common Factor, a.k.a. GCD) of two numbers can be found with a remarkably short recursive rule:

• If b == 0, the HCF is a.
• Otherwise, the HCF of a and b is the same as the HCF of b and a % b.

Before coding: you already have a way to compute a remainder --- recursive_divide(a, b) from Part 5 returns (quotient, remainder). Instead of writing a % b again, how would you get that same remainder by calling recursive_divide?

Your plan:

remainder of a divided by b, using Part 5's function = ...

Write compute_hcf(a, b) using Euclid's method, reusing recursive_divide from Part 5 to get the remainder instead of using %.

Example:

compute_hcf(12, 18)     # Output: 6
compute_hcf(100, 25)    # Output: 25
compute_hcf(17, 13)     # Output: 1
compute_hcf(0, 5)       # Output: 5

You have 3 pegs: A (source), B (auxiliary), C (target), and a stack of discs on A, smallest on top. Move the whole stack to C, one disc at a time, never placing a larger disc on a smaller one.

The general rule for n discs, moving from source to target using auxiliary as spare space:

1. Move the top n - 1 discs from source to auxiliary (using target as spare).
2. Move disc n from source to target.
3. Move the n - 1 discs from auxiliary to target (using source as spare).

Before coding:

1. What's the base case --- the smallest n you can solve directly, with no sub-problem?
2. For n = 2: write out the 3 moves yourself, in order, using the rule above (you have 1 disc to move in steps 1 and 3, and disc 2 in step 2).
3. Notice that steps 1 and 3 are themselves smaller Tower of Hanoi problems --- just with the roles of the three pegs swapped around. This is what makes it recursive twice per call.

Your derivation:

• base case: n = ..., move disc 1 from source to target.
• for n=2: move ... from ... to ..., move ... from ... to ..., move ... from ... to ...

Write solve_hanoi(n, source='A', auxiliary='B', target='C') that:

• prints each move exactly in the format Moving <disc> from <source> to <target>.
• uses the three-step rule above (two recursive calls plus one move printed in between),
• returns the total number of moves performed.

Example:

solve_hanoi(1)
# Moving 1 from A to C.
# Returns: 1

Tasks:

1. Run solve_hanoi(2). You should see exactly 3 moves, matching what you traced by hand in Exercise 7.1.
2. Run solve_hanoi(3). You should see exactly 7 moves.
3. Run solve_hanoi(4) and just look at the returned total (don't worry about reading all the printed moves). What's the pattern in the totals for n = 1, 2, 3, 4? Can you guess the formula for the total number of moves as a function of n?
   • Hint: look back at Part 3 or 4 --- your power/compute_power function might help you verify your guess.

The Tower of Hanoi for n discs requires $2^n - 1$ moves. For n = 4 (four discs), how many moves are needed?

A. 8

B. 15

C. 16

D. 31

The Fibonacci sequence is defined recursively: fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n >= 2.

Tasks:

1. Write fib(n) using plain recursion (two recursive calls, just like Tower of Hanoi).
2. Test it on fib(10) (expected: 55).
3. Time how long fib(30) takes. Then try fib(35). What's happening? (Hint: how many times does fib end up computing fib(2), for instance?)
4. Fix the slowness using memoization: keep a dictionary that caches fib(n) the first time you compute it, and check the cache before recursing. How much faster is fib(35) now?

In Exercise 7.3, you may have guessed that solve_hanoi(n) always returns $2^n - 1$ total moves.

Write a small check that uses your compute_power function from Part 4 to verify this formula against the actual return value of solve_hanoi, for n from 1 to 10 (call solve_hanoi in a way that doesn't print anything, or just ignore the printed output).

Take a moment to answer these questions in your own words.

1. Every recursive function you wrote has a base case and a recursive case. What goes wrong if a function is missing a base case, or if the recursive case never gets closer to the base case?
2. In Part 2, how did handling a negative b show you a pattern: solve the "hard" case by converting it to a case you already know how to solve?
3. In Part 6, what did you reuse from Part 5, and why was that better than rewriting the remainder logic with %?
4. Tower of Hanoi and Fibonacci both make two recursive calls per step, instead of one. What's different about how their total work grows as n increases?
5. What is memoization, and what problem does it solve?