Хвост Рекурсивный подсчет в схеме

Question

Функция должна быть рекурсивной и считать от 1 до указанного числа.Я думаю, что я довольно близко.Вот что у меня есть:

(define (countup l)
  (if (= 1 l) 
      (list l)
      (list
       (countup (- l 1))
       l
       )
    )
  )

Однако, это, очевидно, возвращает список с вложенными списками.Я попытался использовать функцию добавления вместо второго списка безрезультатно.Любое руководство?

Answer 1

Вы должны использовать вспомогательную функцию для реализации хвостово-рекурсивного решения этой проблемы (функция «цикла») и использовать дополнительный параметр для накопления ответа. Примерно так:

(define (countup n)
  (loop n '()))

(define (loop i acc)
  (if (zero? i)
      acc
      (loop (sub1 i) (cons i acc))))

В качестве альтернативы, вы можете использовать именованное let. В любом случае, решение является хвостово-рекурсивным, и для накопления значений используется параметр, обратите внимание, что рекурсия продвигается назад , начиная с n и считая обратно до 0, заключая каждое значение по очереди в начало списка:

(define (countup n)
  (let loop ((i n)
             (acc '()))
    (if (zero? i)
        acc
        (loop (sub1 i) (cons i acc)))))

Answer 2

Вот неправильное решение:

(define (countup n)
  (define (help i)
    (if (<= i n)
        (cons i (help (+ i 1)))
        '()))
  (help 1))

Это решение:

• использует вспомогательную функцию
• рекурсивно по числам от 1 до n,занося их в постоянно растущий список

Почему это неправильно?Это не совсем хвостовая рекурсия, потому что она создает большую длинную строку вызовов cons, которые не могут быть оценены немедленно.Это может привести к переполнению стека при достаточно больших значениях n.

Вот лучший способ решения этой проблемы:

(define (countup n)
  (define (help i nums)
    (if (> i 0)
        (help (- i 1)
              (cons i nums))
        nums)))
  (help n '()))

Примечания:

• это решение лучше, потому что вызовы cons могут быть оценены немедленно, поэтому эта функция является кандидатом для оптимизации хвостовой рекурсии (TCO), и в этом случае пространство стека не будет проблемой.
• help рекурсивно повторяет числа в обратном порядке, что исключает необходимость использования append, что может быть довольно дорогим

Answer 3

Предполагая, что это для учебного упражнения, и вы хотите такое поведение:

(countup 5) => (list 1 2 3 4 5)

Вот подсказка - в хвостовой рекурсивной функции вызов в хвостовой позиции должен быть сам по себе (если толькоявляется крайним регистром).

Так как отсчет не принимает список чисел, вам понадобится функция-накопитель, которая принимает число и список и возвращает список.

Вот шаблон:

;; countup : number -> (listof number)
(define (countup l)

  ;; countup-acc : number, (listof number) -> (listof number)
  (define (countup-acc c ls)
    (if ... 
        ...
        (countup-acc ... ...)))

  (countup-acc l null))

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

Answer 4

Вот рабочая версия вашего кода, которая возвращает список в правильном порядке (я заменила l на n):

(define (countup n)
 (if (= 1 n) 
     (list n)
     (append (countup (- n 1)) (list n))))

К сожалению, есть проблема с этим фрагментом кода: это не хвостовая рекурсия.Причина в том, что рекурсивный вызов countup не находится в хвостовой позиции.Это не в хвостовой позиции, потому что я делаю добавление результата (countup (- l 1)), поэтому хвостовой вызов равен append (или list при n = 1), а не countup.Это означает, что этот фрагмент кода является нормальной функцией с повторным получением, но с хвостовой рекурсивной функцией.

Проверьте эту ссылку из Википедии, чтобы получить лучший пример того, почему это не хвостовой возврат.1016 *

Чтобы сделать его хвостовой рекурсивной, вам понадобится аккумулятор, ответственный за накопление подсчитанных значений.Таким образом, вы сможете поместить рекурсивный вызов функции в конечную позицию.Обратите внимание на разницу в ссылке, которую я вам дал.

Не стесняйтесь отвечать, если вам нужна дополнительная информация.