схема - Является ли функция хвостовой рекурсивной?

Я реализовал эту рекурсивную функцию в схеме:

       (define f (lambda (n)

        (cond ((= n 0) 0)
              ((= n 1) 2)
              ((= n 2) 37)
              ((odd? n) (+ (f (- n 3)) 1))
              (else (+ (f (- (/ n 2) 1)) 7))))
        )

Во многих упражнениях меня спрашивали, является ли мое решение хвостовой рекурсией или нет, и, честно говоря, независимо от того, сколько раз я читал определение хвостовой рекурсии, я просто не понимаю его. Если бы я определил хвостовую рекурсию, это было бы примерно так.

Определение: хвостовая рекурсивная функция вычисляется в постоянном пространстве памяти независимо от входного значения.

Вот еще два. Один из них хвостовой рекурсивный, и я хочу выяснить, какой именно.

(define ln2-a
 (lambda (n)
 (define loop
   (lambda (n)
     (if (= n 1)
         0
        (+ 1 (loop (quotient n 2))))))
 (trace loop)
 (loop n)))

И тут.

(define ln2-b
  (lambda (n)
    (define loop
      (lambda (n result)
      (if (= n 1)
         result
       (loop (quotient n 2) (+ result 1)))))
 (trace loop)
 (loop n 0)))

Давайте посмотрим на две последние функции. Здесь я предполагаю, что ln2-b - рекурсивный. Но я не могу ответить почему, что меня как бы раздражает. Я думаю, что цикл трассировки мне помогает, НО я не совсем уверен, что он говорит и как мне помогает. Я пытаюсь сравнить все три функции, найти сходства, а также то, чем они отличаются друг от друга. Но, к сожалению, у меня не получается ...

Надеюсь, кто-нибудь дружелюбный сможет мне помочь, спасибо. Да, к тому же я новичок в информатике, поэтому, возможно, я неправильно использую терминологию. Если что-то непонятно, просто скажи. :)


recursion scheme tail-recursion
person jopp    schedule 14.09.2015    source источник
comment
Вызов функции называется хвостовой рекурсией, если после возврата из функции нечего делать, кроме как вернуть ее значение. Итак, ln2-b - это tr, поскольку вся работа выполняется до рекурсии. С ln-2a loop вызывается рекурсивно, и по возвращении из цикла к результату добавляется 1.   -  person Johnny Mopp    schedule 14.09.2015

Ответы (3)


arrow_upward
4
arrow_downward

В вашем первом блоке кода f не является хвостовой рекурсией. Рекурсивный вызов f должен произойти, вернуть его результат, а затем к результату нужно добавить 1 или 7, в зависимости от ветви. Поскольку вызов рекурсивного вызова f должен возвращаться, и существует произвольно много рекурсивных вызовов f, это означает, что необходимо выделить произвольно много кадров стека.

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

Например, рассмотрим два способа вычисления длины списка:

(define (length-1 list)
  (if (null? list)
      0
      (+ 1
         (length-1 (cdr list))))) ; recursive call, NOT a tail-call

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

(define (length-2 list current-length)
  (if (null? list)
      current-length
      (length-2 (cdr list) ; recursive call, IS a tail-call
                (+ 1 current-length))))

В этой версии, как только вы начнете выполнять рекурсивный вызов length-2, вам больше не нужен контекст из исходного вызова. Фактически, вы можете преобразовать это в цикл, назначив (список cdr) на список и назначив < strong> (+ 1 current-length) до current-length. Вы можете повторно использовать то же пространство стека. Вот как оптимизация хвостового вызова (когда хвостовой вызов относится к той же функции) эквивалентна циклу.

person Joshua Taylor    schedule 14.09.2015
comment
Хорошо, спасибо. Итак, если бы я удалил оператор + плюс (и, конечно же, 1 и 7), он был бы хвостовой рекурсией? :) - person jopp; 14.09.2015
comment
@Joel Да, будет (хотя, конечно, он больше не будет вычислять то же значение). - person Joshua Taylor; 14.09.2015
comment
Ах, понятно, спасибо вам большое, тогда я гораздо лучше понимаю, что такое хвостовая рекурсия. Хотел бы я дать вам положительный голос, но мне нужно больше репутации. :) - person jopp; 14.09.2015
comment
@Joel Обратите внимание, что оптимизация хвостового вызова предназначена не только для рекурсии. если у вас есть функция foo, определенная, например, (define (foo x) (bar (list x x))), то вызов bar находится в хвостовой позиции. Поскольку вам не нужен контекст из foo при вызове bar, пространство стека может быть немедленно освобождено. Хвостовые вызовы - это больше, чем просто хвостовая рекурсия. - person Joshua Taylor; 14.09.2015

arrow_upward
0
arrow_downward

Хвостовая рекурсивная функция будет передавать накопленный результат в каждый вызов, так что после достижения конечного условия результат может быть немедленно возвращен этим последним вызовом функции.

Неактуальная рекурсивная функция потребует каких-либо действий с результатом после его возврата. Итак, каждый уровень рекурсии необходимо запомнить, чтобы он мог вернуться назад и вычислить окончательный результат.

В вашем первом примере вы добавляете результат следующего вызова f, поэтому он не является хвостовым рекурсивным.

Второй пример также добавляет к следующему вызову цикла, поэтому он не является хвостовым рекурсивным.

В третьем примере конечный результат передается в качестве аргумента в следующий вызов функции, поэтому он является хвостовым рекурсивным.

person Luke Fritz    schedule 14.09.2015

arrow_upward
0
arrow_downward

Это очень просто ... Когда вам нужно что-то сделать с результатом рекурсии, это не хвостовая рекурсия.

(define (length lst)
  (if (null? lst)
      0
      (+ 1
         (length (cdr lst))))

Здесь вы ясно видите, что мы должны + 1 ответить на рекурсию. Это происходит на каждом шаге, поэтому стек накапливается до тех пор, пока не будет достигнут базовый вариант, и мы добавим 1 для каждого элемента на обратном пути. (length '(1 2 3 4)) ; ==> (+ 1 (+ 1 (+ 1 (+ 1 0))))

Когда процедура завершена и результат является результатом последнего шага (базовый случай), она является хвостовой рекурсией.

(define (length lst)
  (define (aux lst count)
    (if (null? lst)
        count ; last step
        (aux (cdr lst) (+ 1 count))))

  (aux lst 0))

Здесь вспомогательная процедура имеет count в качестве аргумента, и вместо того, чтобы ждать добавления 1, вы делаете это до того, как произойдет рекурсия (путем увеличения аргумента). Результат всего этого - просто результат базового случая и не более того. Это хвостовая рекурсия. Даже вызов помощника является хвостовым вызовом, но не рекурсивным, но все хвостовые вызовы оптимизированы в Scheme.

Итак, какая из ваших двух процедур хвостовая рекурсивная?

person Sylwester    schedule 14.09.2015