Какое определение для "естественная рекурсия"?

Question

Третья заповедь Маленького интрижка гласит:

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

Каково точное определение "естественной рекурсии"? Причина, по которой я спрашиваю, состоит в том, что я беру урок по принципам языка программирования Даниэля Фридмана, и следующий код не считается "естественно рекурсивным":

(define (plus x y)
    (if (zero? y) x
        (plus (add1 x) (sub1 y))))

Однако следующий код считается "естественно рекурсивным":

(define (plus x y)
    (if (zero? y) x
        (add1 (plus x (sub1 y)))))

Я предпочитаю "неестественно рекурсивный" код, потому что он хвостовой рекурсивен. Однако такой код считается анафемой. Когда я спросил, почему мы не должны писать функцию в хвостовой рекурсивной форме, тогда помощник инструктора просто ответил: "Вы не возитесь с естественной рекурсией".

В чем преимущество написания функции в "естественно-рекурсивной" форме?

Answer 1

"Естественная" (или просто "структурная") рекурсия - лучший способ начать обучение студентов рекурсии. Это потому, что у него есть замечательная гарантия, на которую указывает Джошуа Тейлор: она гарантированно прекратит [*]. Студентам достаточно трудно обдумать такую ​​программу, и если сделать это "правилом", это может спасти их от удара головой о стену.

Когда вы решаете покинуть сферу структурной рекурсии, вы (программист) берете на себя дополнительную ответственность, которая заключается в том, чтобы гарантировать, что ваша программа останавливается на всех входах; это еще одна вещь, чтобы подумать и доказать.

В вашем случае это немного более тонко. У вас есть два аргумента, и вы делаете структурно рекурсивные вызовы для второго. Фактически, с этим наблюдением (программа является структурно рекурсивной по аргументу 2), я бы сказал, что ваша оригинальная программа в значительной степени так же легитимна, как и программа, не вызывающая хвост, поскольку она наследует то же доказательство сходимости. Спросите Дэна об этом; Мне было бы интересно услышать, что он говорит.

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

Answer 2

Естественная рекурсия связана с "естественным", рекурсивным определением типа, с которым вы имеете дело. Здесь вы работаете с натуральными числами; поскольку "очевидно" натуральное число либо равно нулю, либо является преемником другого натурального числа, когда вы хотите построить натуральное число, вы, естественно, выводите 0 или же (add1 z) для некоторых других природных z что происходит вычисляется рекурсивно.

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

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

Поначалу помощник инструктора не очень помогал ("возиться с естественной рекурсией" звучит как "не спрашивай"), но подробное объяснение, которое он дал в приведенном вами снимке, было более уместным.

Answer 3

(define (plus x y)
(if (zero? y) x
    (add1 (plus x (sub1 y)))))

когда y != 0 он должен помнить, что как только результат (plus x (sub1 y)) известно, он должен вычислить add1 в теме. Следовательно, когда у достигает нуля, рекурсия достигает своего пика. Теперь начинается этап возврата и add1исполнены. Этот процесс можно наблюдать с помощью trace,

Я сделал трассировку для:

(require racket/trace)
(define (add1 x) ...)
(define (sub1 x) ...)
(define (plus x y) ...)
(trace plus)

(plus 2 3)

Вот след:

>(plus 2 3)
> (plus 2 2)
> >(plus 2 1)
> > (plus 2 0)  // Deepest point of recursion
< < 2           // Backtracking begins, performing add1 on the results
< <3
< 4
<5
5               // Result

Разница в том, что другая версия не имеет фазы возврата. Он вызывает себя несколько раз, но итеративен, потому что запоминает промежуточные результаты (передаваемые в качестве аргументов). Следовательно, процесс не занимает дополнительного места.

---

Иногда реализовать хвостовую рекурсивную процедуру проще или элегантнее, чем писать ее итеративный эквивалент. Но для некоторых целей вы не можете / не можете реализовать это рекурсивным способом.

PS: у меня был класс, который немного рассказывал об алгоритмах сборки мусора. Такие алгоритмы могут не быть рекурсивными, так как может не быть свободного места, следовательно, нет места для рекурсии. Я помню алгоритм под названием "Deutsch-Schorr-Waite", который поначалу было действительно трудно понять. Сначала он реализовал рекурсивную версию, просто чтобы понять концепцию, затем он написал итеративную версию (следовательно, вручную, чтобы помнить, откуда в памяти он пришел), поверьте мне, рекурсивная версия была намного проще, но не могла использоваться на практике...