Recursion in Python

Introduction

Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem. It is particularly useful for problems that can be broken down into smaller, repetitive tasks. This article explains recursion in Python with examples.

How Recursion Works

A recursive function must have:

• A base case: The condition that stops the recursion.
• A recursive case: The part where the function calls itself with a smaller problem.

Example: Factorial of a Number

The factorial of a number n is the product of all positive integers less than or equal to n. It can be calculated recursively as:

    n! = n * (n-1)!
        

The following example demonstrates a recursive function to calculate the factorial:

    # Recursive function to calculate factorial
    def factorial(n):
        if n == 0 or n == 1:  # Base case
            return 1
        return n * factorial(n - 1)  # Recursive case

    # Calling the function
    result = factorial(5)
    print("Factorial of 5 is:", result)
        

Output:

    Factorial of 5 is: 120
        

Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The recursive formula is:

    F(n) = F(n-1) + F(n-2)
        

With the base cases:

    F(0) = 0, F(1) = 1
        

The following example demonstrates a recursive function to calculate Fibonacci numbers:

    # Recursive function to calculate Fibonacci numbers
    def fibonacci(n):
        if n == 0:  # Base case
            return 0
        if n == 1:  # Base case
            return 1
        return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

    # Calling the function
    for i in range(10):
        print(f"Fibonacci({i}) =", fibonacci(i))
        

Output:

    Fibonacci(0) = 0
    Fibonacci(1) = 1
    Fibonacci(2) = 1
    Fibonacci(3) = 2
    Fibonacci(4) = 3
    Fibonacci(5) = 5
    Fibonacci(6) = 8
    Fibonacci(7) = 13
    Fibonacci(8) = 21
    Fibonacci(9) = 34
        

Example: Sum of a List

Recursion can be used to calculate the sum of elements in a list:

    # Recursive function to calculate the sum of a list
    def sum_list(numbers):
        if len(numbers) == 0:  # Base case
            return 0
        return numbers[0] + sum_list(numbers[1:])  # Recursive case

    # Calling the function
    numbers = [1, 2, 3, 4, 5]
    result = sum_list(numbers)
    print("Sum of the list is:", result)
        

Output:

    Sum of the list is: 15
        

Advantages and Disadvantages of Recursion

Advantages:

• Simplifies code for problems that can be divided into smaller subproblems.
• Useful for problems involving tree traversal, graph traversal, and divide-and-conquer algorithms.

Disadvantages:

• Can lead to high memory usage due to deep recursion.
• May cause stack overflow if the base case is not properly defined or the recursion is too deep.

Conclusion

Recursion is a powerful tool in Python that simplifies solving complex problems by breaking them into smaller subproblems. While it makes code more elegant and readable for certain tasks, it should be used with caution to avoid performance issues. Experiment with these examples to understand recursion better.