Beginner-Friendly Topic
Take your time - it's perfectly normal to re-read this topic 2-3 times. Try the interactive code editor below to run code yourself. Use the Q&A section to check your understanding before moving on. You've got this! 🚀
Recursion
Recursion is when a function calls itself. Every recursive function needs a base case (stopping condition) to prevent infinite recursion. It's elegant for problems that have a natural recursive structure.
Recursion
# Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120
def factorial(n):
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
print(factorial(5)) # 120
print(factorial(10)) # 3628800
# Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, ...
def fibonacci(n):
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
for i in range(10):
print(fibonacci(i), end=" ") # 0 1 1 2 3 5 8 13 21 34
print()
# Sum of digits: 1234 → 1 + 2 + 3 + 4 = 10
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
print(f"Sum of digits in 1234: {digit_sum(1234)}") # 10
# Python's recursion limit (default: 1000)
import sys
print(f"Recursion limit: {sys.getrecursionlimit()}")Tip
Tip
Python has a recursion limit of 1000 by default. For deep recursion, use iteration or increase it with sys.setrecursionlimit(). But prefer iteration for large inputs.
Functions are first-class objects in Python - pass them, return them, store them
Common Mistake
Warning
Forgetting the base case causes infinite recursion and RecursionError. Every recursive function MUST have a condition that stops the recursion.
Practice Task
Note
(1) Write factorial using recursion. (2) Write Fibonacci. (3) Write digit_sum(1234) = 10. (4) Convert one to an iterative version.