Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until it reaches a base case. It is commonly used for problems that can be broken down into smaller subproblems, such as factorial computation, Fibonacci sequence, tree traversal, and more.

Recursion is a method where a function calls itself directly or indirectly to solve a problem. It consists of two main parts:

1. Base Case – The condition where the recursion stops.
2. Recursive Case – The function calls itself with modified parameters, moving toward the base case.

The factorial of a number n is defined as:

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

Example: 5! = 5 × 4 × 3 × 2 × 1 = 120

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

print(factorial(5))  # Output: 120

A function calls itself directly.

def direct_recursion(n):
    if n == 0:
        return
    print(n)
    direct_recursion(n - 1)

A function calls another function, which in turn calls the first function.

def func1(n):
    if n > 0:
        print(n)
        func2(n - 1)

def func2(n):
    if n > 0:
        print(n)
        func1(n - 2)

func1(5)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # Output: 8

def reverse_string(s):
    if len(s) == 0:
        return s
    return s[-1] + reverse_string(s[:-1])

print(reverse_string("hello"))  # Output: "olleh"

def tower_of_hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n - 1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, source, target)

tower_of_hanoi(3, 'A', 'B', 'C')

Python has a recursion depth limit (default: 1000 calls). If a function recurses too many times, it may cause a RecursionError.

import sys
print(sys.getrecursionlimit())  # Output: 1000

sys.setrecursionlimit(2000)  # Changing recursion depth limit

If recursion goes too deep, Python raises:

RecursionError: maximum recursion depth exceeded

• When the problem is naturally recursive (e.g., tree traversal, graph traversal).
• When writing a recursive solution is simpler and more readable than an iterative one.
• When you can ensure that the recursion won’t exceed memory limits.

• Avoid recursion when an iterative approach is more efficient.
• Avoid recursion if memory constraints are a concern.

1. Factorial of a number nikalne ke liye recursive function likho. ➤ Example: factorial(5) = 120

2. Fibonacci series ka nth term recursive function se find karo. ➤ Example: fibonacci(6) = 8

3. Sum of first n natural numbers recursively nikalne ka program likho. ➤ Example: sum_n(5) = 15

4. Reverse a string using recursion. ➤ Example: reverse("hello") = "olleh"

5. Find the sum of digits of a given number using recursion. ➤ Example: sum_digits(1234) = 10

6. Check palindrome string using recursion. ➤ Example: "madam" → True, "hello" → False

7. Find GCD (Greatest Common Divisor) of two numbers using recursion. ➤ Example: gcd(48, 18) = 6

8. Calculate power of a number (xⁿ) using recursion. ➤ Example: power(2, 5) = 32

9. Count number of elements in a list recursively (without using len()). ➤ Example: count([1, 2, 3, 4]) = 4

10. Find maximum element in a list using recursion. ➤ Example: max_recursive([5, 2, 9, 1, 7]) = 9