Python Recursion

Recursion is a technique where a function calls itself to solve a problem. A recursive function must have a base case to stop the recursion; otherwise, it will run indefinitely.

Basic Recursion Example

Example

def countdown(n):
    if n == 0:
        print("Done")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

Output:

5
4
3
2
1
Done

Understanding the Base Case

The base case is the condition that stops the recursive function from calling itself.

Example

def show_number(num):
    if num == 1:
        print(num)
        return

    print(num)
    show_number(num - 1)

show_number(3)

Output:

3
2
1

Recursion with Return Value

Example

def add_numbers(n):
    if n == 1:
        return 1

    return n + add_numbers(n - 1)

print(add_numbers(5))

Output:

15

Finding Factorial Using Recursion

The factorial of a number is the product of all positive integers less than or equal to that number.

Example

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

    return n * factorial(n - 1)

print(factorial(5))

Output:

120

Finding Fibonacci Series Using Recursion

Example

def fibonacci(n):
    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))

Output:

8

Infinite Recursion Example

If a base case is not provided, Python raises a recursion error.

Example

def test():
    test()

test()

Output:

RecursionError: maximum recursion depth exceeded

Advantages of Recursion

• Makes code shorter and cleaner.
• Useful for solving complex problems.
• Commonly used in tree and graph algorithms.
• Helps break large problems into smaller problems.

Summary

• Recursion is when a function calls itself.
• Every recursive function should have a base case.
• The base case prevents infinite recursion.
• Recursive functions can return values.
• Recursion is commonly used for factorials, Fibonacci series, trees, and algorithms.
• Missing a base case results in a RecursionError.