Python Recursion — Full Detailed Notes

What is Recursion?

In recursion, a function solves a small part of the problem and calls itself to solve the rest.

It is commonly used in tree traversal, searching, sorting, and mathematical problems like factorial and Fibonacci.

You must be careful with recursion, otherwise it can cause infinite calls or stack overflow errors.

A Simple Recursive Example

A recursive countdown function:

def countdown(n):
  if n <= 0:
    print("Done!")
  else:
    print(n)
    countdown(n - 1)

countdown(5)

Base Case & Recursive Case

Every recursive function must have two parts:

• Base Case — Stops the recursion.
• Recursive Case — Function calls itself with a smaller/simpler input.

Without a base case, recursion never stops and causes a stack overflow.

Example: Factorial Function

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

print(factorial(5))

Fibonacci Sequence (Recursive)

The Fibonacci sequence is defined such that each number is the sum of the previous two.

Sequence: 0, 1, 1, 2, 3, 5, 8, ...

def fibonacci(n):
  if n <= 1:
    return n
  else:
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))

Recursion with Lists

Recursion can handle lists by working with one element at a time and recursing on the rest.

Example: Sum of a List

def sum_list(numbers):
  if len(numbers) == 0:
    return 0
  else:
    return numbers[0] + sum_list(numbers[1:])

my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))

Example: Find Maximum in List

def find_max(numbers):
  if len(numbers) == 1:
    return numbers[0]
  else:
    max_of_rest = find_max(numbers[1:])
    return numbers[0] if numbers[0] > max_of_rest else max_of_rest

my_list = [3, 7, 2, 9, 1]
print(find_max(my_list))

Recursion Depth Limit

Python limits recursion depth to prevent crashes. The default limit is usually around 1000.

Check current recursion limit

import sys
print(sys.getrecursionlimit())

Increase recursion limit

Be careful — setting it too high can crash your program.

import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())

When to Use Recursion?

Recursion is ideal when:

• Problems can be divided into smaller similar subproblems
• Working with trees, graphs, or nested structures
• Problems are naturally recursive (factorial, Fibonacci, permutations)

Use recursion wisely for clean, elegant solutions — but always make sure you have a clear base case and that each step moves closer to it.