🔁 Python Recursion — Functions That Call Themselves

Introduction 🌟

Recursion is a programming technique where a function calls itself to solve a problem. Each recursive call breaks the problem into smaller subproblems until a stopping condition is reached.

Note

💡 Every recursive function MUST have a base case to prevent infinite recursion.

1. Basic Concept 🧱

basic_recursion.py

def greet(n):
    if n == 0:     # base case
        return
    print("Hello")
    greet(n - 1)   # recursive call

greet(3)

✔️ Prints "Hello" 3 times.
✔️ greet(n - 1) reduces the problem size.

2. Components of Recursion 🔍

  • Base Case → Stops the recursion.
  • Recursive Case → Function calls itself with smaller input.
  • Progress → Each call must move toward the base case.

3. Factorial Using Recursion ✖️

factorial.py

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

Note

✔️ Classic example of recursion.
✔️ Function keeps calling itself until n becomes 1.

4. Sum of First N Numbers ➕

sum_recursive.py

def sum_n(n):
    if n == 1:
        return 1
    return n + sum_n(n - 1)

print(sum_n(5))  # 15

5. Fibonacci Using Recursion 🌀

Fibonacci series: 0, 1, 1, 2, 3, 5, 8…

fibonacci.py

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

print(fib(6))  # 8

Note

⚠️ Recursive Fibonacci is slow—calls grow exponentially. Use memoization to optimize.

6. Printing a Countdown ⏳

countdown.py

def countdown(n):
    if n == 0:
        print("Start!")
        return
    print(n)
    countdown(n - 1)

countdown(5)

7. Recursion with Strings 🔤

Reverse a String

reverse_string.py

def reverse(s):
    if s == "":
        return ""
    return reverse(s[1:]) + s[0]

print(reverse("python"))

8. Recursion with Lists 📦

Sum of List Elements

list_sum.py

def list_sum(lst):
    if len(lst) == 0:
        return 0
    return lst[0] + list_sum(lst[1:])

print(list_sum([1, 2, 3, 4]))

9. Nested Structures Recursion 🪜

nested_sum.py

def nested_sum(lst):
    total = 0
    for item in lst:
        if isinstance(item, list):
            total += nested_sum(item)
        else:
            total += item
    return total

print(nested_sum([1, [2, 3], [4, [5]]]))

10. Limitations of Recursion ⚠️

  • Too deep recursion can cause a RecursionError.
  • Not always memory-efficient.
  • Iterative solutions may be faster.

recursion_error.py

# Python's default recursion limit is around 1000
import sys
print(sys.getrecursionlimit())

11. Tail Recursion (Python Does NOT Optimize) ❌

Some languages optimize tail recursion (last operation is the recursive call). Python does NOT — the recursion depth still grows.

tail_recursion_example.py

def tail_fact(n, acc=1):
    if n == 1:
        return acc
    return tail_fact(n - 1, n * acc)

12. When to Use Recursion 🎯

  • Tree or graph traversal
  • Divide and conquer algorithms (merge sort, quick sort)
  • Working with nested lists or structures
  • Mathematical problems (factorial, Fibonacci)

13. Real-World Examples 🌍

Directory Traversal

directory_traversal.py

import os

def explore(path):
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        if os.path.isdir(full_path):
            explore(full_path)
        else:
            print(full_path)

# explore("C:/Users/...")

Binary Search (Recursive)

binary_search.py

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

    mid = (low + high) // 2

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

print(binary_search([10, 20, 30, 40, 50], 40, 0, 4))

Conclusion 🎉

>>“Recursion breaks big problems into smaller pieces — elegant, powerful, and beautiful.” ✨

You now fully understand Recursion in Python! Want the next topic? Try Modules, Decorators, Classes & Objects (OOP), or Error Handling. Just tell me! 😊