Recursion

 Recursion

Recursion is a programming concept in which a function calls itself as a subroutine to solve a problem. Recursive solutions break down complex problems into simpler, more manageable subproblems, making it easier to solve the overall problem. Here's an example of recursion in Python along with an explanation:

### Example: Factorial using Recursion

Factorial of a non-negative integer \( n \) is denoted as \( n! \) and is the product of all positive integers from \( 1 \) to \( n \). The factorial of \( n \) is calculated as \( n! = n \times (n-1) \times (n-2) \times .... \times 1 \).

```python

def factorial(n):

    # Base case: factorial of 0 or 1 is 1

    if n == 0 or n == 1:

        return 1

    else:

        # Recursive call to calculate factorial

        return n * factorial(n-1)

# Calculate factorial of 5

result = factorial(5)

print("Factorial of 5:", result)  # Output: Factorial of 5: 120

```

In this example, we define a function `factorial()` that calculates the factorial of a given non-negative integer \( n \). The base case is when \( n \) is \( 0 \) or \( 1 \), in which case we return \( 1 \). For any other \( n \), we recursively call the `factorial()` function with \( n-1 \) and multiply it by \( n \) to calculate the factorial.

### Recursion Process for \( n = 5 \):

1. `factorial(5)` calls `factorial(4)` -> \( 5 \times \text{factorial}(4) \)

2. `factorial(4)` calls `factorial(3)` -> \( 5 \times 4 \times \text{factorial}(3) \)

3. `factorial(3)` calls `factorial(2)` -> \( 5 \times 4 \times 3 \times \text{factorial}(2) \)

4. `factorial(2)` calls `factorial(1)` -> \( 5 \times 4 \times 3 \times 2 \times \text{factorial}(1) \)

5. `factorial(1)` returns \( 1 \) (base case)

6. Recursive calls unwind: \( 5 \times 4 \times 3 \times 2 \times 1 = 120 \)

Recursion is a powerful technique used in algorithms and problem-solving. However, it's important to define proper base cases to prevent infinite recursion and ensure the algorithm terminates successfully.