def count_down(n):
    # Базовый случай: когда достигли 0, останавливаемся
    if n == 0:
        print("Готово!")
        return
    
    # Выводим текущее число
    print(n)
    
    # Рекурсивный шаг: вызываем функцию с n-1
    count_down(n - 1)

count_down(5)

5
4
3
2
1
Готово!

def factorial(n):
    # Базовый случай
    if n == 0 or n == 1:
        return 1
    
    # Рекурсивный шаг
    return n * factorial(n - 1)

print(factorial(5))  # 120

# Для значения 3

factorial(3)
│
├─ factorial(2)  ← добавляется в стек
│  │
│  ├─ factorial(1)  ← добавляется в стек
│  │  └─ возвращает 1  ← снимается со стека
│  │
│  └─ возвращает 2  ← снимается со стека
│
└─ возвращает 6  ← снимается со стека

Шаг 1: [factorial(3)]
Шаг 2: [factorial(3), factorial(2)]
Шаг 3: [factorial(3), factorial(2), factorial(1)]
Шаг 4: [factorial(3), factorial(2)]  ← factorial(1) вернул результат
Шаг 5: [factorial(3)]  ← factorial(2) вернул результат
Шаг 6: []  ← factorial(3) вернул результат

def sum_numbers(n):
    # Базовый случай
    if n == 0:
        return 0
    
    # Рекурсивный шаг
    return n + sum_numbers(n - 1)

print(sum_numbers(5))  # 15 (5+4+3+2+1)

def power(base, exponent):
    # Базовый случай
    if exponent == 0:
        return 1
    
    # Рекурсивный шаг
    return base * power(base, exponent - 1)

print(power(2, 3))  # 8 (2 * 2 * 2)

def string_length(s):
    # Базовый случай: пустая строка
    if s == "":
        return 0
    
    # Рекурсивный шаг: убираем первый символ и считаем остаток
    return 1 + string_length(s[1:])

print(string_length("hello"))  # 5

def fibonacci(n):
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Рекурсивный шаг
    return fibonacci(n - 1) + fibonacci(n - 2)

# Примеры
print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(5))   # 5
print(fibonacci(10))  # 55

**Почему так медленно?**

Посмотрим на дерево вызовов для fibonacci(5):

Однако у этой наивной реализации есть серьёзный недостаток — экспоненциальная временная сложность O(2^n). Это происходит из-за колоссального количества повторных вычислений одних и тех же значений, что хорошо видно на дереве вызовов для `fibonacci(5)`, где, например, `fibonacci(3)` вычисляется несколько раз. Для оптимизации применяют технику мемоизации — сохранения результатов предыдущих вычислений в кеше (словаре), чтобы не считать их заново.

```python
def fibonacci_memo(n, memo={}):
    # Если уже вычисляли, берем из кеша
    if n in memo:
        return memo[n]
    
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Вычисляем и сохраняем результат
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Работает быстро!

def count_down(n):
    # Базовый случай: когда достигли 0, останавливаемся
    if n == 0:
        print("Готово!")
        return
    
    # Выводим текущее число
    print(n)
    
    # Рекурсивный шаг: вызываем функцию с n-1
    count_down(n - 1)

count_down(5)

5
4
3
2
1
Готово!

def factorial(n):
    # Базовый случай
    if n == 0 or n == 1:
        return 1
    
    # Рекурсивный шаг
    return n * factorial(n - 1)

print(factorial(5))  # 120

# Для значения 3

factorial(3)
│
├─ factorial(2)  ← добавляется в стек
│  │
│  ├─ factorial(1)  ← добавляется в стек
│  │  └─ возвращает 1  ← снимается со стека
│  │
│  └─ возвращает 2  ← снимается со стека
│
└─ возвращает 6  ← снимается со стека

# Стек вызовов для factorial(3):

Шаг 1: [factorial(3)]
Шаг 2: [factorial(3), factorial(2)]
Шаг 3: [factorial(3), factorial(2), factorial(1)]
Шаг 4: [factorial(3), factorial(2)]  ← factorial(1) вернул результат
Шаг 5: [factorial(3)]  ← factorial(2) вернул результат
Шаг 6: []  ← factorial(3) вернул результат

def sum_numbers(n):
    # Базовый случай
    if n == 0:
        return 0
    
    # Рекурсивный шаг
    return n + sum_numbers(n - 1)

print(sum_numbers(5))  # 15 (5+4+3+2+1)

def power(base, exponent):
    # Базовый случай
    if exponent == 0:
        return 1
    
    # Рекурсивный шаг
    return base * power(base, exponent - 1)

print(power(2, 3))  # 8 (2 * 2 * 2)

def string_length(s):
    # Базовый случай: пустая строка
    if s == "":
        return 0
    
    # Рекурсивный шаг: убираем первый символ и считаем остаток
    return 1 + string_length(s[1:])

print(string_length("hello"))  # 5

def fibonacci(n):
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Рекурсивный шаг
    return fibonacci(n - 1) + fibonacci(n - 2)

# Примеры
print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(5))   # 5
print(fibonacci(10))  # 55

# Почему так медленно?

Посмотрим на дерево вызовов для fibonacci(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
              /    \      /    \
          fib(3) fib(2) fib(2) fib(1)
          /   \   /  \   /  \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /   \
  fib(1) fib(0)

def fibonacci_memo(n, memo={}):
    # Если уже вычисляли, берем из кеша
    if n in memo:
        return memo[n]
    
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Вычисляем и сохраняем результат
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Работает быстро!