What is Recursive Thinking?
- Recursive thinking is a problem-solving approach where a problem is broken down into smaller, similar as original problem subproblems.
- This approach is particularly useful when a problem can be defined in terms of itself.
Definition
Recursion
Process when function calls itself within its own definition/body.
Recursive method calls itself until some terminating condition is met. This is accomplished without any specific repetition construct, such as a while or a for loop.
Key Characteristics of Recursion
Base Case: A condition that stops the recursion, preventing infinite loops.
AnalogyYou can think of the base case as a termination condition.
And Recursive Case: The part of the function where it calls itself with a smaller or simpler input.
Analogy- When action is defined before the recursive case, you can think of recursion like a set of nested Russian dolls.
- Each doll contains a smaller doll, and the process continues until you reach the smallest doll, which represents the base case.
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!- When action is defined before the recursive case, you can think of recursion like pulling out a tape measure.
- You don't read the measurement as you pull — you wait until the end, then read it backwards as you rewind.
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!- When designing a recursive algorithm, always start by defining the base case.
- This ensures that the recursion will eventually terminate.
Identifying Situations for Recursive Thinking
Why Use Recursive Thinking?
- Simplifies Complex Problems: Recursion can make complex problems more straightforward to understand and solve by breaking them into smaller, manageable parts.
- Recursive Nature of Certain Problems: Some problems, like tree traversal or fractal generation, are naturally recursive.
Recursion is commonly used in:
- Mathematical Problems: Factorials, Fibonacci sequences, and combinatorial problems.
- Data Structures: Traversing trees and graphs.
- Fractals and Graphics: Generating complex patterns and shapes.
Why Not Use Recursive Thinking?
- Resource efficiency: Recursive algorithms can be elegant but may have higher memory usage due to the call stack.
- 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.
Any algorithm that can be presented in a recursive manner can also be presented iteratively, although additional data structures may be required, and vice versa.
ExampleThe difference in complexity between the recursive and iterative approaches in the Fibonacci Sequence number generator:
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))- When analysing a problem, ask yourself:
- Can this problem be divided into smaller, similar problems?
- If so, recursion might be a suitable approach.
Real World examples
TipCommon recursive patterns:
- Divide and Conquer: Breaks the problem into smaller, independent subproblems.
- Self-Similarity: Ensures each subproblem is a smaller version of the original problem.
- Base Case: Defines a clear stopping condition to prevent infinite recursion.
Towers of Hanoi
The Towers of Hanoi is a classic example of a problem that can be solved recursively.
