5.1.1 Recognizing Recursive Thinking Notes

What is Recursive Thinking?

1. Recursive thinking is a problem-solving approach where a problem is broken down into smaller, similar as original problem subproblems.
2. This approach is particularly useful when a problem can be defined in terms of itself.

Key Characteristics of Recursion

Base Case: A condition that stops the recursion, preventing infinite loops.

And Recursive Case: The part of the function where it calls itself with a smaller or simpler input.

def open_dolls(n):
    if n == 1: # Termination condition
        print("Reached the smallest doll!")
        return
      
    # Action
    print(f"Opening doll {n}")
    
    # Recursive case
    open_dolls(n - 1)

open_dolls(3) # Try experimenting with Russian dolls!

def measure_tape(n): # An example of recursive method
    # Base case
    if n == 0:
        print("Start of the tape!")
        return # End execution

    # Recursive case
    measure_tape(n - 1)

    # Action
    print(f"Measuring mark at {n}")

measure_tape(5) # Try experimenting with 5-unit measurement tape!

Identifying Situations for Recursive Thinking

Why Use Recursive Thinking?

1. Simplifies Complex Problems: Recursion can make complex problems more straightforward to understand and solve by breaking them into smaller, manageable parts.
2. Recursive Nature of Certain Problems: Some problems, like tree traversal or fractal generation, are naturally recursive.

Why Not Use Recursive Thinking?

1. Resource efficiency: Recursive algorithms can be elegant but may have higher memory usage due to the call stack.
2. Complexity: Recursive algorithms are believed to be more challenging to code than iterative solutions because of the additional defined functions and object references or pointers.

def fib_recursive(n):
    # Base cases: the first two numbers in the Fibonacci sequence
    if n == 1:
        return 0  # First Fibonacci number
    elif n == 2:
        return 1  # Second Fibonacci number

    # Recursive case: F(n) = F(n-1) + F(n-2)
    # The function calls itself to calculate the previous two Fibonacci numbers
    return fib_recursive(n - 1) + fib_recursive(n - 2)

def fib_iterative(n):
    # Base cases
    if n == 1:
        return 0  # First Fibonacci number
    elif n == 2:
        return 1  # Second Fibonacci number

    # Initialize the first two Fibonacci numbers
    prev = 0  # This represents F(1)
    curr = 1  # This represents F(2)

    # Loop starts from 3 because F(1) and F(2) are already known
    for _ in range(3, n + 1):
        next_fib = prev + curr  # Add the two previous numbers
        prev = curr             # Shift prev to the last number
        curr = next_fib         # Move curr to the new Fibonacci number

    return curr  # Return the nth Fibonacci number

# Print the 10th Fibonacci number using both methods
print(fib_recursive(10))
print(fib_iterative(10))

Real World examples

Towers of Hanoi

The Towers of Hanoi is a classic example of a problem that can be solved recursively.

You are given:

• Three rods: A (source), B (auxiliary), and C (destination).
• N disks of different sizes stacked in increasing size on rod A (largest at bottom).

Goal: Move all disks from rod A to rod C using rod B as an auxiliary.

Rules:

1. Only one disk can be moved at a time.
2. You can only move the top disk of any rod.
3. A larger disk cannot be placed on top of a smaller disk.

Recursive Solution:

1. Move n-1 discs from rod A to rod B (using rod C as auxiliary).
2. Move the nth disc from rod A to rod C.
3. Move n-1 discs from rod B to rod C (using rod A as auxiliary).

def tower_of_hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    # Move n-1 disks from source to auxiliary, so they are out of the way
    tower_of_hanoi(n-1, source, target, auxiliary)
    # Move the nth disk from source to target
    print(f"Move disk {n} from {source} to {target}")
    # Move the n-1 disks from auxiliary to target
    tower_of_hanoi(n-1, auxiliary, source, target)


# Example usage:
n_disks = 3
tower_of_hanoi(n_disks, "A", "B", "C")

Koch Snowflake

The Koch snowflake is a fractal that demonstrates recursive thinking in a geometric context.

Construction Steps:

1. Start with an equilateral triangle.
2. For each line segment:
   1. Divide the segment into three equal parts.
   2. Draw an equilateral triangle on the middle segment.
   3. Remove the base of the triangle.

New equilateral triangles are continually created to allow the process to continue endlessly.

Upgrade to Pro to view this video

View plans