Рекурсивная процедура к хвостовой рекурсивной процедуре

Я пытаюсь построить процедуру хвостовой рекурсии из другой процедуры, которую я уже построил. Но я не совсем осознаю, как я должен думать. Я приведу вам два примера, где первый — моя процедура, не являющаяся хвостовой рекурсией, а второй — моя «попытка» сделать хвостовую рекурсивную процедуру. Ага... попытка :) Буду рад любым советам, как строить хвостовые рекурсивные процедуры, с чего начинать, думать и т.д.

Изменить: первый работает именно так, как я хочу. (define square (lambda (x) (* x x)))

(do-to-each square '(1 2 3)) должен возвести каждое число в квадрат, то есть составить список (1 4 9)

(define do-to-each
  (lambda (proc lst)
    (if (list-empty? lst)
        (list-create)
          (list-insert (proc (list-first lst)) (do-to-each proc (list-rest lst))))))

(define do-to-each-tail
  (lambda (proc lst)
    (define loop
      (lambda (n result)
        (if (= n 1)
            (list result)
            (if (eq? (length result) 1)
                (car result)
                (loop (- n 1) (cons (car result) (do-to-each-tail proc (cdr result))))))))
    (loop (length lst) lst)))

recursion scheme tail-recursion racket
person jopp    schedule 08.10.2015    source источник
comment
Связано: stackoverflow.com/q/27386520/124319   -  person coredump    schedule 08.10.2015
comment
А, спасибо, посмотрю на это. :)   -  person jopp    schedule 08.10.2015
comment
Самый простой способ работать с хвостом списка, результат заканчивается в обратном порядке, а затем вы просто снова переворачиваете результат, когда возвращаете его в базовом случае.   -  person leppie    schedule 08.10.2015
comment
По моему опыту, всякий раз, когда я набираю длину, я знаю, что нахожусь на неверном пути, и начинаю сначала.   -  person molbdnilo    schedule 08.10.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

Например, используя вашу нотацию для операций со списками, вот как выглядит возможное решение — и обратите внимание, как мы вызываем вспомогательную процедуру цикла с начальным значением для накопленного результата, а после этого мы reverse выводим:

(define do-to-each-tail
  (lambda (proc lst)
    (define loop
      (lambda (lst result)
        (if (list-empty? lst)
            result
            (loop (list-rest lst)
                  (list-insert (proc (list-first lst)) result)))))
    (reverse (loop lst (list-create)))))

Он работает так, как ожидалось:

(do-to-each-tail square '(1 2 3))
=> '(1 4 9)
person Óscar López    schedule 08.10.2015