Python Recursion

Recursion is a programming concept where a function calls itself in order to solve a problem. In Python, a recursive function is a function that performs a task in part and delegates the remaining task to itself. Each recursive call reduces the original problem to a simpler or smaller subproblem until a base case is reached.

Here's the basic structure of a recursive function:

def recursive_function(parameters):
    # Base case(s)
    if base_case_condition:
        return base_case_result
    
    # Recursive case(s)
    else:
        # Perform some task
        # Call the function with modified parameters
        return recursive_function(modified_parameters)

Example: Factorial Using Recursion

def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    
    # Recursive case
    else:
        return n * factorial(n - 1)

# Example usage
result = factorial(5)
print(f"The factorial of 5 is: {result}")

In this example, the factorial function calculates the factorial of a number n using recursion. The base case is when n is 0 or 1, in which case the factorial is 1. In the recursive case, the function multiplies n by the factorial of (n - 1).

Example: Fibonacci Sequence Using Recursion

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

# Example usage
result = fibonacci(6)
print(f"The 6th Fibonacci number is: {result}")

In this example, the fibonacci function calculates the n-th Fibonacci number using recursion. The base cases are when n is 0 or 1, in which case the function returns 0 or 1, respectively. In the recursive case, the function returns the sum of the previous two Fibonacci numbers.

Recursion provides an elegant way to solve certain types of problems, but it should be used judiciously. It's important to ensure that there is a well-defined base case, and the recursive calls move towards that base case. Otherwise, the recursion may lead to an infinite loop.