Python function recursion

Recursion is a programming technique in which a function calls itself to solve a problem. It can be a powerful way to solve problems that can be broken down into smaller, similar subproblems. In this tutorial, we'll explore how to use recursion in Python.

Base case: A simple case that can be solved without further recursion. The base case helps to stop the recursion and prevent infinite loops.
Recursive case: The case where the function calls itself with a simpler or smaller version of the problem, moving closer to the base case.

Let's look at an example of a recursive function to calculate the factorial of a number:

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

Here's how the function works for factorial(5):

factorial(5) -> 5 * factorial(4)
factorial(4) -> 4 * factorial(3)
factorial(3) -> 3 * factorial(2)
factorial(2) -> 2 * factorial(1)
factorial(1) -> 1 (base case)
The function then starts returning values and multiplying them together, resulting in the final factorial value of 120.

Another example is the Fibonacci sequence:

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

Here's how the function works for fibonacci(5):

fibonacci(5) -> fibonacci(4) + fibonacci(3)
fibonacci(4) -> fibonacci(3) + fibonacci(2)
fibonacci(3) -> fibonacci(2) + fibonacci(1)
fibonacci(2) -> fibonacci(1) + fibonacci(0)
fibonacci(1) -> 1 (base case)
fibonacci(0) -> 0 (base case)
The function starts returning values and adding them together, resulting in the final Fibonacci value of 5.

Note: While recursion can be elegant, it can also be inefficient, particularly for problems like the Fibonacci sequence where the same subproblems are calculated repeatedly. In such cases, consider using other techniques like memoization or dynamic programming.

How to write recursive functions in Python:
- Description: Explore the syntax and structure of recursive functions.
- Code:
```
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
```