Skip to main content

Recursion in Python

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem.
It is often used to break down complex problems into smaller, simpler sub-problems.

Basic Structure of Recursion​

Every recursive function has two main parts:

  1. Base Case → Stops the recursion (prevents infinite calls).
  2. Recursive Case → Function calls itself with modified input.

Example:

def countdown(n):
    if n == 0:   # Base case
        print("Time's up!")
    else:        # Recursive case
        print(n)
        countdown(n-1)

countdown(5)
Output:
# 5
# 4
# 3
# 2
# 1
# Time's up!

Factorial using Recursion​

Factorial of n → n! = n × (n-1) × (n-2) × ... × 1

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

print(factorial(5))  # Output: 120

Fibonacci Series using Recursion​

Fibonacci sequence → 0, 1, 1, 2, 3, 5, 8, ...

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

for i in range(7):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8

Recursion vs Iteration​

  • Iteration (loops): Uses for or while loops.
  • Recursion: Function calls itself.

Example: Sum of first n numbers

Recursive:

def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n-1)

print(sum_recursive(5))  # Output: 15

Iterative:

def sum_iterative(n):
    total = 0
    for i in range(1, n+1):
        total += i
    return total

print(sum_iterative(5))  # Output: 15

Advantages of Recursion​

Makes code shorter and cleaner Useful for problems naturally defined recursively (factorial, Fibonacci, tree traversal, divide and conquer algorithms)

Disadvantages of Recursion​

Slower execution than iteration (due to repeated function calls) Memory usage is high (function calls are stored in the call stack) Risk of stack overflow error if base case is missing

Tail Recursion in Python​

Tail recursion is when the recursive call is the last statement in the function. Unlike some languages, Python does not optimize tail recursion, so deep recursion may cause errors.

def tail_sum(n, accumulator=0):
    if n == 0:
        return accumulator
    return tail_sum(n-1, accumulator+n)

print(tail_sum(5))  # Output: 15

Practical Example: Binary Search (Recursive)​

def binary_search(arr, target, low, high):
    if low > high:
        return -1   # Not found

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid+1, high)
    else:
        return binary_search(arr, target, low, mid-1)

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7, 0, len(nums)-1))  # Output: 3

Conclusion​

  • Recursion is a function calling itself to solve smaller sub-problems.
  • Every recursive function must have a base case to avoid infinite calls.
  • Useful for problems like factorial, Fibonacci, searching, sorting, and tree/graph traversal.
  • While recursion makes code elegant, it may be slower and consume more memory than iteration.