Python recursion | Python

Recursion in Python

Recursion is a technique in which a function calls itself to solve a problem. Instead of using loops, recursion breaks a big problem into smaller, similar subproblems and solves them step by step.

A recursive function keeps calling itself until a specific condition is met. This stopping condition is called the base case. Without a base case, the function will call itself forever and the program will crash.

In simple terms:

Recursion = a function solving a problem by calling itself on a smaller version of the same problem.

Why Recursion Is Used

Recursion is useful when a problem can be naturally divided into smaller parts that follow the same pattern.

Common examples include:

Factorial calculation
Fibonacci series
Tree and graph traversal
Divide and conquer algorithms

Basic Structure of Recursion

A recursive function has two main parts:

Base Case → Stops the recursion
Recursive Case → Calls the function again with a smaller problem

Example: Factorial Using Recursion

The factorial of a number is defined as:

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

Recursive solution:

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

print(factorial(5))

Step-by-Step Explanation

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1
= 120

The recursion stops when n == 1.

Example: Fibonacci Series

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

print(fibonacci(6))

This function keeps breaking the problem into smaller Fibonacci values.

Real-Life Analogy

Think of two mirrors facing each other.

You see the same image repeated again and again, but it becomes smaller each time.

Recursion works in a similar way — the same function repeats with a smaller problem until it reaches the final point.

Recursion vs Loop

Recursion:

Solves problems in a mathematical and elegant way
Best for tree-like and divide-and-conquer problems

Loops:

Faster and use less memory
Better for simple repetition

Common Mistake

If the base case is missing, recursion becomes infinite.

Example of wrong recursion:

def func():
    return func()

This will crash the program.

Conclusion

Recursion is a powerful technique where a function calls itself to solve smaller versions of a problem. It makes complex problems easier to express and is widely used in advanced programming concepts like trees, graphs, and algorithms. Understanding recursion is an important step toward deeper problem-solving in Python.