Recursion – python

Recursive Functions in Python

In Python, a recursive function is a function that calls itself to solve a problem. A recursive function usually solves a large problem by breaking it down into smaller, more manageable problems that can be solved identically.

A recursive function always has to have some base condition that stops the recursion, otherwise, the function will call itself indefinitely.

Example: Factorial Function

The factorial of a number n (written as n!) is the product of all positive integers less than or equal to n. Here’s how we can calculate a factorial using a recursive function in Python:

def factorial(n):
    # base condition
    if n == 0 or n == 1:
        return 1
    else:
        # recursive call
        return n * factorial(n - 1)
        
print(factorial(5))  # Output: 120

Example: Fibonacci Function

The Fibonacci sequence is where each number is the sum of the two preceding ones, usually starting with 0 and 1. Here’s how we can generate the Fibonacci sequence using a recursive function in Python:

def fibonacci(n):
    # base conditions
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        # recursive call
        return fibonacci(n-1) + fibonacci(n-2)
        
print(fibonacci(10))  # Output: 55

Please note that while recursion can be an elegant solution for certain problems, it can also be inefficient for large inputs because of repeated computations and can lead to a stack overflow for very deep recursions. For such situations, other methods like iteration or dynamic programming might be more appropriate.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top