Схема: смена рекурсии на хвостовую рекурсию

Question

Я не уверен, как превратить обратный отсчет в хвостовую рекурсивную программу. Он принимает неотрицательное число n и возвращает список целых чисел от 0 до n (включая n).

Редактировать: Хорошо, я наконец-то получил этот на работу. Проблема заключалась не в том, что моя текущая программа была рекурсивной, и мне нужно было сделать ее хвостовой рекурсивной. Это было просто неправильно. Фактический ответ очень короткий и чистый. Так что, если кто-то еще застрял на этом и является полным новичком в программировании, вот несколько советов, которые могут помочь:

1) Ваша вспомогательная программа предназначена для отслеживания списка до сих пор.

2) Базовый случай: если х = 0, что ты делаешь? добавить 0 на .. что-то.

3) Повторите x - 1, а затем добавьте x в свой список.

4) Когда вы доберетесь до своей действительной программы, все, что вам нужно, это помощник. Но помните, что требуется два аргумента!

Answer 1

Единственная рекурсивная функция здесь - это обратный список. Это хвостовая рекурсия, потому что сам вызов является последней операцией в теле функции.

Ваша функция для генерации неубывающей последовательности от нуля до m, которая содержит последовательные результаты добавления 1 к предыдущему элементу, будет выглядеть примерно так:

(define (my-reverse lst)
  (define (rev-do xs ys)
    (if (empty? xs)
        ys
        (rev-do (cdr xs) (cons (car xs) ys))))
  (rev-do lst empty))

(define (seq m n)
  (seq-do m n (list m)))

(define (seq-do m n xs)
  (if (= m n)
      (my-reverse xs)
      (let ((next (add1 m)))
        (seq-do next n (cons next xs)))))

(define (seq-from-zero m)
  (seq 0 m))

Тест:

> (seq-from-zero 10)
(0 1 2 3 4 5 6 7 8 9 10)

seq-do - общая функция для генерации неубывающих последовательностей от m до n; это хвостовая рекурсия, потому что последняя операция - это вызов самой себе.

Я также реализовал reverse с нуля, чтобы вы могли использовать его в своих домашних заданиях.