lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

pythonIntroStep3Chapter4Title

pythonIntroStep3Chapter1Title

pythonIntroStep3Chapter2Title

pythonIntroStep3Chapter3Title

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

print("fibonacci(1):", fibonacci(1))
print("fibonacci(2):", fibonacci(2))
print("fibonacci(3):", fibonacci(3))  
print("fibonacci(4):", fibonacci(4))  
print("fibonacci(5):", fibonacci(5))
print("fibonacci(6):", fibonacci(6))

# Functions That Call Themselves - Recursive Functions

A `recursive function` is a function that calls itself within its own definition and continues to **execute repetitively** until a certain condition (base case) is met.

<br />

## Example of Recursive Function

Below is an example of a recursive function that calculates the product of numbers from `1` to the `given number`.

```python title="Factorial Recursive Function Example"
# n! = 1 * 2 * 3 * ... * n
def factorial(n):
    # Base case: when n is 1
    if n == 1:
        # Return 1 and terminate the recursive calls
        return 1
    else:
        # Multiply n by the value returned from factorial invoked with n - 1
        return n * factorial(n - 1)

# Function call
print(factorial(5))
# 120
```

<br />

## When to Use Recursive Functions?

Recursive functions are used to perform repetitive tasks such as calculating the `factorial(!)` of numbers, or generating `Fibonacci sequences` (a sequence where each number is the sum of the two preceding ones).

They can also be utilized in `algorithms` for searching or manipulating data.

```python title="Fibonacci Sequence Function Example"
def fibonacci(n):
    # Base case: return n when n is 1 or less
    if n <= 1:
        return n
    # When n is 2 or more
    else:
        # Return the sum of the (n-1)th and (n-2)th Fibonacci numbers
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))
# 8
```

A recursive function works by calling itself. By calling itself, it can simplify complex problems.

### What is the most suitable word to fill in the blank below?