Схема: Какая ошибка в моем коде рекурсии хвоста?

(define log2_tail 
    (lambda (n) 
    (letrec ((log2 (lambda (n res) 
         (if (= n 1) 
          res 
          (log2 (quotient (+ n 1) 2) (+ 1 res)))))) 
     (log2 n 0)))) 
(log2_tail 3)

Выше код представляет собой схему хвостовой рекурсии для вычисления целочисленной части базы данных журнала 2. (На самом деле я не уверен). Но если я выполню с аргументом 3, результат будет равен 2 не 1. Я предполагаю, что это потому, что Я использую letrec, тогда как я могу его решить?Схема: Какая ошибка в моем коде рекурсии хвоста?

источник

2013-04-07 Joshua Park

Не добавляйте 1 при вычислении частного. –

@Terje D. Ой, я не думаю об изменении этой части, спасибо. Тогда мне интересно, что это хвостовая рекурсия. –

Обратите внимание, что более понятный способ написать это с именем named let; что позволяет более легко сфокусироваться на функциональности. Как это.

(define (log2_tail n) 
    (let log2 ((n n) (res 0)) 
    (if (= n 1) 
     res 
     (log2 (quotient n 2) 
       (+ 1 res)))))

А «имени пусть» переводится в letrec компилятором.

источник

2013-04-07 21:33:56 GoZoner

Я написал +1, потому что это правильно, но один незначительный nit-pick: он называется 'let', а не' named let'. (Например, посмотрите на документ R5RS, и вы увидите, что он набирается таким же образом.) –

Исправлено. Тонкий ... – GoZoner

Спасибо, я не привык к другой форме. Тогда это правильная хвостовая рекурсия? –

Схема: Какая ошибка в моем коде рекурсии хвоста?

ответ

Смежные вопросы