Рекурсивна процедура към опашка-рекурсивна процедура

Опитвам се да конструирам рекурсивна процедура от друга процедура, която вече съм конструирал. Но не съм напълно наясно как трябва да мисля. Давам ви два примера, където първият е моята процедура, която не е опашка рекурсивна, а вторият е моят „опит“ да направя опашно рекурсивна процедура. Да... опит :) Ще се радвам на всякакви съвети как да конструирам опашни рекурсивни процедури, как да започна, да мисля и каквото и да било.

Редактиране: Първият работи точно както искам. (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