Рекурсию как процесс изучают еще на уроках информатики в школе. Она часто используется при разработке алгоритмов и обходе структур данных. Рекурсивная функция вызывает свою копию и решает меньшие подзадачи исходных задач. При создании программ этот метод можно использовать для упрощения кода. В статье мы расскажем, что такое рекурсия в программировании, в чем разница между рекурсивным и итеративным процессом.
- Определение рекурсии
- Примеры рекурсивных функций
- Рекурсивный процесс
- Определение
- Преимущества и недостатки
- Итеративный процесс
Определение рекурсии
Рекурсия — это процесс, в котором функция неоднократно вызывает сама себя. Рекурсивная функция сначала проверяет, выполняется ли базовое условие. Если нет, она вызывает себя с измененным входным параметром. При этом создается новый экземпляр с другим набором локальных переменных. Процесс повторяется до выполнения стартового условия.
Пример вычисления рекурсивных алгоритмов — факториал. Это произведение всех натуральных чисел до заданного числа n. Факториал n можно вычислить рекурсивно, путем умножения n на факториал (n-1) до тех пор, пока не будет достигнуто условие n=1.
Рекурсия используется для выполнения сложных задач, таких как обход древовидной и графовой структуры. Один из плюсов использования рекурсивного подхода — код становится лаконичным. Но даже если размер кода и количество вычислений уменьшится, потребуется много ресурсов: рекурсивность включает в себя несколько вызовов ввода-вывода.
Примеры рекурсивных функций
Быстрая сортировка — это алгоритм, который использует рекурсию для сортировки списка объектов. Он работает путем разделения списка на два других. Один содержит элементы меньше, чем опорный элемент. Второй содержит элементы, превышающие опорный. Алгоритм рекурсивно сортирует каждый подсписок.
Еще один случай — последовательность Фибоначчи. Она представляет собой серию чисел, в которой каждое число — это сумма двух предыдущих чисел. Последовательность Фибоначчи можно вычислить рекурсивно, путем сложения двух предыдущих чисел до тех пор, пока не будет достигнут базовый случай 0 или 1. После этого цикл завершится.
Например, нужно найти максимальное значение в списке чисел. Это либо первое число, либо наибольшее из оставшихся. Так будет выглядеть код:
Function find_max( list )
possible_max_1 = first value in list
possible_max_2 = find_max ( rest of the list );
if ( possible_max_1 > possible_max_2 )
answer is possible_max_1
else
answer is possible_max_2
end
Функция в Python, которая выводит факториал заданного числа:
def factorial(n):
# Base case: if n is 0 or 1, return 1
f n == 0 or n == 1:
return 1
# Recursive case: if n is greater than 1, call the function with n-1 and multiply by n
else:
return n * factorial(n-1)
# Call the factorial function and print the result
result = factorial(5)
print(result) # Output: 120
Для вызова рекурсии в функции используются следующие шаги.
1. Установка основного случая. Выберите наиболее простую ситуацию, для которой очевиден ответ. Это условие остановки рекурсии, которое не позволит функции бесконечно вызывать себя.
2. Описание процесса с использованием мелких составляющих. Рекурсивный вызов функции позволит решить каждую задачу, разбив ее на более мелкие версии самой себя.
3. Конечность цикла. Убедитесь, что простой код не переходит в бесконечный цикл и в итоге достигает базового случая.
4. Объединение всех решений. Чтобы выполнить главную задачу, объедините решения всех подзадач.
Рекурсивный процесс
Итерацию и рекурсию часто путают между собой. Оба эти термина относятся к двум разным структурам кода с одной и той же конечной целью: повторное выполнение набора последовательных инструкций.
Определение
Рекурсивный процесс — процесс вызова функции внутри ее собственного кода. При определении рекурсии нужно определить условие выхода. Иначе цикл будет бесконечным. Поэтому рекурсивный подход требует наложения условия завершения рекурсии. Код рекурсивности короче итеративного кода, но его не всегда легко понять. Рекурсивные функции используются для решения различных задач — нахождения факториала числа, создания ряда Фибоначчи.
Преимущества и недостатки
Одно из преимуществ рекурсии — быстрое решение определенных типов задач. Это уменьшает количество ошибок в коде. Рекурсивный метод бывает эффективней, чем итерационный подход, например, при работе с определенными структурами данных — рекурсивный метод упрощает процесс обхода. Рекурсивный код также можно обобщить для обработки различных входных данных.
Хвостовая рекурсия положительно сказывается на эффективности готовых программ. При этом методе рекурсивный вызов считается последней операцией в функции. Это позволяет компилятору или интерпретатору оптимизировать ее. Повторно используется один и тот же кадр стека для каждого вызова. Так пропадает необходимость в дополнительном пространстве. Этот случай называется оптимизацией хвостового вызова. Он в разы повышает эффективность функций и предотвращает ошибки переполнения стека.
Рекурсивность может быть менее эффективной, чем итеративный подход. Это заметно при работе с большими входными данными: каждый вызов функции требует дополнительной памяти для поддержания стека. Рекурсию также сложнее отлаживать. Стек вызовов может стать многосоставным. Это затрудняет определение основной причины ошибки. В некоторых случаях рекурсия может быть не такой интуитивно понятной, как итерация. Разработчикам становится сложнее понять код, следовательно, усложняется его поддержка.
Итеративный процесс
Итерация — это повторение вычислительного процесса, который продолжается до тех пор, пока управляющее условие не станет ложным. Если же условие цикла не становится ложным, возникает бесконечный цикл. Итеративный процесс завершается, когда условие цикла перестанет выполняться. Итерация потребляет меньше памяти, но делает код длиннее, что затрудняет его чтение и редактирование.