Как заставить эту схему функционировать не хвостовой рекурсивно? - PullRequest
Новая
       63

Как заставить эту схему функционировать не хвостовой рекурсивно?

1 голос
/ 27 сентября 2019

Я не могу понять, как сделать так, чтобы эта хвостовая рекурсивная схема больше не была хвостовой рекурсивной.Кто-нибудь, кто может мне помочь? 

(define (foldrecl f x u)
  (if (null? x)
      u 
      (foldrecl f (cdr x) (f (car x) u))))

Ответы [ 2 ]

1 голос
/ 27 сентября 2019

влево сгибы наследуются по итерациям, но вы можете легко сделать их рекурсивными, добавив продолжение.например.

(let ((value expresion-that-calculates))
  value)

Итак, в вашем случае: 

(define (foldrecl f x u)
  (if (null? x)
      u 
      (let ((result (foldrecl f (cdr x) (f (car x) u))))
        result)))

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

(define (fold-right proc tail lst)
  (if (null? lst)
      tail
      (cons (proc (car lst))
            (fold-right proc tail (cdr lst)))))

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

Также обратите внимание, что немного проще увидеть, какие аргументы используются, когда при вызове процедуры proc, хвост результата tail и аргумент списка lst.Вам даже не нужно читать мой код, чтобы знать, как его использовать, но вы не представляете, что x и u, и ti не помогает тому, что порядок аргументов не соответствует ни одной реализации foldизвестный в схеме.

0 голосов
/ 27 сентября 2019

Рекурсивный вызов находится в хвостовой позиции, поэтому поместите его в другой вызов процедуры, например так: 

(define (identity x) x)

(define (foldrecl f x u)
  (if (null? x)
      u 
      (identity (foldrecl f (cdr x) (f (car x) u)))))

теперь рекурсивный вызов не находится в хвостовой позиции, он больше не является хвостовой рекурсивностью.

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

...