Recursion is when a function calls itself to solve a problem.
It keeps calling itself until a base condition (stopping condition) is reached.

Think of it like repeatedly asking the same question until the answer becomes simple enough to solve.

---

1️⃣ Basic Structure of Recursion

def function_name(parameters):
    if base_condition:
        return result
    else:
        return function_name(smaller_problem)

Two important parts:

1. Base Case → stops the recursion
2. Recursive Call → function calls itself

---

Example 1: Factorial using Recursion

Factorial formula:$$n! = n \times (n-1)!$$n!=n×(n−1)!

Example:

5! = 5 × 4 × 3 × 2 × 1

Code

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

Output

120

How it Works

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

---

Example 2: Sum of Numbers

Calculate:

1 + 2 + 3 + ... + n

Code

def sum_numbers(n):
    if n == 1:
        return 1
    else:
        return n + sum_numbers(n-1)print(sum_numbers(5))

Output

15

---

Example 3: Fibonacci Series

Fibonacci pattern:

0 1 1 2 3 5 8 13

Formula:

F(n) = F(n-1) + F(n-2)

Code

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

Output

8

---

⚠️ Important Rule

Every recursive function must have a base case.

Without it, Python will show an error:

RecursionError: maximum recursion depth exceeded

Example of wrong recursion:

def test():
    return test()test()

---

When Recursion is Useful

Recursion is commonly used in:

• Factorials
• Fibonacci series
• Tree structures
• File systems
• Algorithms (DFS, backtracking)

---

✅ Quick Comparison

Method	Description
Loop	Uses for or while
Recursion	Function calls itself