Recursion is a technique in programming where a function calls itself to solve a problem.

What is Recursion?

A recursive function is a function that:

1. Calls itself
2. Has a base case to stop recursion

Syntax of Recursive Function

def recursive_function():
   if condition:       # base case
       return result
   else:
       return recursive_function()  # recursive call

Example 1: Recursive Countdown

def countdown(n):
   if n == 0:
       print("Lift off!")
   else:
       print(n)
       countdown(n - 1)
countdown(5)

Output:

5
4
3
2
1
Lift off!

Example 2: Factorial Using Recursion

The factorial of a number n is:

n! = n × (n-1) × (n-2) × ... × 1

Recursive Formula:

factorial(n) = n * factorial(n-1)
factorial(1) = 1  (base case)

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

Output:

120

Example 3: Fibonacci Series Using Recursion

Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, ...

Recursive Formula:

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
fibonacci(0) = 0
fibonacci(1) = 1

def fibonacci(n):
   if n <= 1:
       return n
   else:
       return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6))  # Output: 8

Be Careful!

Recursive functions can lead to infinite recursion if no proper base case is defined.

# Infinite loop example (❌)
def bad_recursion():
   return bad_recursion()
# This will cause: RecursionError: maximum recursion depth exceeded

Recursion vs Loop

Tail Recursion (Note)

Python does not optimize tail recursion, unlike some languages. So too many recursive calls may lead to a RecursionError.

Practice Task

Write a recursive function to compute the sum of numbers from 1 to n:

def recursive_sum(n):
   if n == 1:
       return 1
   else:
       return n + recursive_sum(n - 1)
print(recursive_sum(5))  # Output: 15

Summary

• Recursion is powerful but must include a base case.
• Best for divide-and-conquer problems: factorial, fibonacci, tree traversal.
• Avoid deep recursion for large datasets in Python.