Все о рекурсии
Часть 2. Рекурсивный процесс против рекурсивной процедуры и хвостовой рекурсии
В первой части этой серии мы рассказали об основах рекурсии. В этом посте мы поговорим о различиях между рекурсивным процессом и рекурсивной процедурой. Различие легко упустить из виду, но, по сути, рекурсивная процедура — это когда программа вызывает себя внутри своего тела (это определение большинство людей думают, когда говорят о рекурсии), в то время как рекурсивный процесс — это процесс, который выполняется рекурсивно, а не итеративно.
В некоторых компьютерных языках не все процедуры, вызывающие сами себя, выполняются рекурсивно.
Например, в Scheme вы можете вызвать процедуру внутри себя (рекурсивная процедура) и передать счетчик в качестве параметра. После каждого выполнения вызова вы добавляете единицу к счетчику. Каждый раз, когда вы выполняете расчеты, счетчик отслеживает текущее состояние расчета. Компьютеру нужно отслеживать только одно состояние.
Если бы мы хотели вычислить факториал числа 6 (а почему бы не вычислить факториал числа 6?!), мы могли бы определить функцию с именем factorial(n)
, которая принимает число, для которого мы хотим найти факториал (в данном случае 6). и определите другую функцию fact-iter(product, counter, max)
, которая принимает три параметра:
product
— число, которое хранит промежуточную сумму чисел, которые были умноженыcounter
— число, которое отслеживает, какое число в данный момент умножаетсяmax
— сколько раз вы хотели бы повторить этот процесс
(define (factorial n) (fact-iter 1 1 n) (define (fact-iter product counter max) if (> count max) product (fact-iter (* counter product) (+ counter 1) max)))
Из приведенного выше кода видно, что fact-iter
будет обрабатывать логику нахождения факториала, а factorial
запустит процесс. Функция fact-iter
сначала проверит, что текущее количество шагов умножения меньше, чем max
. Если оно больше, чем max
, это означает, что произошло правильное количество умножений, и в этом случае он должен вернуть product
. Если он меньше, чем max
, он должен снова вызвать сам себя (это то, что делает fac-iter
рекурсивной процедурой), однако, поскольку мы передаем обновленные product
и counter
, это делает его итеративным процессом. На каждом этапе рекурсивного вызова компьютер отслеживает обновленное состояние. Нет отложенной операции, которую компьютер должен отслеживать, как это было в примере fib(n)
в части 1 этой серии.
Если вы знакомы с наиболее распространенными языками программирования, вам могут показаться очень похожими циклические конструкции, такие как операторы do
, while
и for
. Схема не имеет этих циклических конструкций и должна использовать рекурсивную процедуру для итерации. Этот процесс использования рекурсии для итерации (в отличие от формального оператора цикла) известен как хвостовая рекурсия, потому что последний вызов в процедуре или операторе (конечная позиция, отсюда и название) только рекурсивный вызов (т.е. при рекурсивном вызове не выполняется никаких дополнительных операций).