Все о рекурсии

Часть 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. Схема не имеет этих циклических конструкций и должна использовать рекурсивную процедуру для итерации. Этот процесс использования рекурсии для итерации (в отличие от формального оператора цикла) известен как хвостовая рекурсия, потому что последний вызов в процедуре или операторе (конечная позиция, отсюда и название) только рекурсивный вызов (т.е. при рекурсивном вызове не выполняется никаких дополнительных операций).