Recursion in Python

What is Recursion in Python?

Recursion in Python is a technique where a function calls itself to solve a problem. It breaks down a problem into smaller sub-problems of the same type.

Key Concepts of Recursion

• Base Case - The condition under which the function stops calling itself
• Recursive Case - The part where the function calls itself with a different argument

Syntax of Recursive Function

def function_name(parameters):
    if base_condition:
        return result
    else:
        return function_name(modified_parameters)

Example 1: Factorial Using Recursion

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

print(factorial(5))

Output:

120

Example 2: Fibonacci Series Using Recursion

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

for i in range(7):
    print(fibonacci(i), end=" ")

Output:

0 1 1 2 3 5 8

Recursive Function Limitation - Stack Overflow

Too many recursive calls can cause a RecursionError.

def infinite():
    return infinite()

infinite()  # Will throw RecursionError

Controlling Recursion Depth

Use sys.setrecursionlimit() to set the maximum recursion depth:

import sys
sys.setrecursionlimit(2000)

When to Use Recursion?

Use recursion when:

• The problem can be broken down into sub-problems of the same type
• You're working with tree structures, mathematical sequences, divide-and-conquer algorithms, etc.

Recursive vs Iterative Approach