Рекурсия в Python

Рекурсия в программировании

Рекурсия в программировании - это процесс, при котором функция вызывает саму себя внутри своего кода. Эта концепция является важной составной частью многих языков программирования, включая Python. Рекурсивные функции могут быть использованы для решения задач, которые могут быть разделены на более мелкие подзадачи.

Для лучшего понимания рекурсии с помощью Python давайте рассмотрим некоторые примеры кода. Начнем с простого примера - вычисления факториала числа.

<pre class="hljs"><code class="python">def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
</code></pre>

В этом примере рекурсивная функция factorial вычисляет факториал числа n. Если значение n равно 0, функция возвращает 1 как базовый случай. В противном случае, она вызывает саму себя с аргументом n-1, умножая его на n. Это позволяет функции постепенно уменьшать входное значение до базового случая.

Вот пример использования функции factorial:

<pre class="hljs"><code class="python">print(factorial(5)) # Вывод: 120
</code></pre>

Когда мы вызываем функцию factorial(5), она вызывает себя с аргументами 4, 3, 2 и 1 до достижения базового случая factorial(0). Затем, функция возвращает значение 1, которое умножается на все предыдущие значения и в конечном итоге дает факториал числа 5, равный 120.

Второй пример - рекурсивная функция для вычисления чисел Фибоначчи:

<pre class="hljs"><code class="python">def fib(n):
    if n <= 1:
        return n
    else:
        return (fib(n-1) + fib(n-2))
</code></pre>

В этом примере функция fib использует рекурсию для вычисления чисел Фибоначчи. Если значение n меньше или равно 1, функция возвращает само число. В противном случае, она вызывает саму себя дважды с аргументами n-1 и n-2, и возвращает сумму этих двух вызовов.

Вот пример использования функции fib:

<pre class="hljs"><code class="python">print(fib(7)) # Вывод: 13
</code></pre>

Когда мы вызываем функцию fib(7), она вызывает себя с аргументами 6 и 5. Затем эти вызовы формируют рекурсию вниз до базовых случаев fib(0) и fib(1). После этого, функция начинает возвращаться обратно к исходному вызову, вычисляя сумму для каждого из них. В результате получаем число Фибоначчи, равное 13.

Рекурсивные функции можно использовать для решения множества задач, и эти примеры лишь демонстрируют базовую концепцию.