схема - Функцията опашка рекурсивна ли е?

Приложих тази рекурсивна функция в схема:

       (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))))
        )

При много упражнения ме питаха дали решението ми е рекурсивна опашка или не и честно казано, колкото и пъти да чета дефиницията за рекурсия на опашката, просто не я разбирам. Ако дефинирам tail-recursive, ще бъде нещо подобно.

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

Ето и още две. Един от тях е tail-recursive и искам да разбера кой.

(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, това означава, че трябва да бъдат разпределени произволно много стекови рамки.

Когато мислите да извикате функция, може да ви помогне да си представите, че вземате нов лист хартия и напишете всички локални променливи и стойности на този лист хартия. Когато определяте резултата от функцията, може да има рекурсивни извиквания на същата функция. Ако повикването е tail-call, тогава, когато вземете лист хартия за него, вие можете да изхвърлите стария лист, тъй като вече не се нуждаете от стойностите му.

Например, разгледайте два начина за изчисляване на дължината на списък:

(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 list) на списък и присвояване < strong>(+ 1 текуща дължина) към текуща дължина. Можете да използвате повторно същото пространство на стека. Ето как оптимизацията на опашката (когато опашката е към същата функция) е еквивалентна на цикъл.

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 в рамките на call to 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