Python Intermediate_011: Recursive Functions in Python

Recursive functions are a powerful programming concept where a function calls itself to solve a problem by breaking it into smaller, similar subproblems. In this tutorial, we’ll explore recursion in depth, starting with the basics and moving on to more complex problems.

 

1. What Are Recursive Functions?

A recursive function solves a problem by calling itself with a modified input, reducing the problem size until it reaches a base case — a condition that stops the recursion. It consists of two key parts:

• Base Case: The condition that stops the recursion.
• Recursive Case: The part where the function calls itself with a smaller or simpler input.

Think of recursion like a stack of tasks: each call adds a layer, and the base case starts resolving them backward.

 

2. Simple Example: Factorial of a Number

The factorial of a number n (denoted as n!) is the product of all positive integers up to n. For example, 4!=4×3×2×1=24.

Here’s a recursive function to calculate the factorial:

def factorial(n):
    if n == 1:  # Base case
        return 1
    else:  # Recursive case
        return n * factorial(n - 1)

print(factorial(4))  # Output: 24

How It Works:

1. factorial(4) → 4 * factorial(3)
2. factorial(3) → 3 * factorial(2)
3. factorial(2) → 2 * factorial(1)
4. factorial(1) → 1 (base case hit)

Then, the results are computed back up:

• 2×1=2
• 3×2=6
• 4×6=24

3. Why Use Recursion?

Recursion is ideal for problems with natural hierarchical or repetitive structures, such as:

• Calculating factorials or Fibonacci numbers.
• Traversing trees or graphs (e.g., file directories).
• Solving puzzles like the Tower of Hanoi.

However, recursion can be memory-intensive due to the call stack, and it may not always be the most efficient solution.

 

4. More Complex Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones (e.g., 0,1,1,2,3,5,8,…0,1,1,2,3,5,8,…). Here’s a recursive implementation:

def fibonacci(n):
    if n <= 1:  # Base case
        return n
    else:  # Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(5))  # Output: 5

How It Works:

1. fibonacci(5) → fibonacci(4) + fibonacci(3)
2. fibonacci(4) → fibonacci(3) + fibonacci(2)
3. fibonacci(3) → fibonacci(2) + fibonacci(1)
4. fibonacci(2) → fibonacci(1) + fibonacci(0)
5. fibonacci(1) → 1 (base case)
6. fibonacci(0) → 0 (base case)

The results are summed back up to compute the final value.

 

5. Problem 1: Power of a Number

Problem: Write a recursive function to calculate the power of a number, e.g., 2³=8.

def power(base, exp):
    if exp == 0:  # Base case
        return 1
    else:  # Recursive case
        return base * power(base, exp - 1)

print(power(2, 3))  # Output: 8

Explanation:

1. power(2, 3) → 2 * power(2, 2)
2. power(2, 2) → 2 * power(2, 1)
3. power(2, 1) → 2 * power(2, 0)
4. power(2, 0) → 1 (base case)

Then, the results are computed back up:

• 2×1=2
• 2×2=4
• 2×4=8

6. Problem 2: Binary Search Using Recursion

Problem: Implement a recursive binary search algorithm to find an element in a sorted list.

def binary_search(arr, target, low, high):
    if low > high:  # Base case: element not found
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:  # Base case: element found
        return mid
    elif arr[mid] > target:  # Search in the left half
        return binary_search(arr, target, low, mid - 1)
    else:  # Search in the right half
        return binary_search(arr, target, mid + 1, high)

arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search(arr, target, 0, len(arr) - 1)
print(f"Element found at index: {result}")  # Output: 3

Explanation:

• The function checks the middle element of the array.
• If the middle element is the target, it returns the index.
• If the target is smaller, it searches the left half; if larger, it searches the right half.
• The process repeats until the target is found or the search space is exhausted.

7. Problem 3: Recursive List Sum

Problem: Write a recursive function to calculate the sum of all elements in a list.

def list_sum(arr):
    if not arr:  # Base case: empty list
        return 0
    else:  # Recursive case
        return arr[0] + list_sum(arr[1:])

arr = [1, 2, 3, 4, 5]
print(list_sum(arr))  # Output: 15

Explanation:

• The function adds the first element of the list to the sum of the remaining elements.
• The process repeats until the list is empty.

— Key Takeaways

• Recursion is a powerful tool for solving problems that can be broken into smaller, similar subproblems.
• Always define a base case to stop the recursion.
• Recursion can be memory-intensive, so use it judiciously.