Я нашел статью, The secret to understanding recursion, что очень смутило меня. Это предполагает, что нет необходимости отслеживать все вызовы рекурсивной функции. В нем также говорится:Нет необходимости трассировать все рекурсивные вызовы функции
Программист, определяющий рекурсивную функцию, обычно не говорит о последовательности вызовов, вызванных ее вызовом.
Я не понимаю этого. Вы можете объяснить?
В контексте он говорит, что, пока каждый шаг приближает вас к базовому корпусу, вы собираетесь туда добраться, и вам не нужно делать пошаговое прохождение алгоритма осознать это.
Возможно, вы видели факториалы в качестве примера? Если вы знаете, что n! = n × (n -1)! шаг правильный, и вы знаете, что 1! = 1 шаг правильный, вам не нужно делать всю арифметику, чтобы получить от 10! = 10 × 9! до 10! = 10 × 9 × 8 ... для проверки алгоритма. Поскольку каждый шаг верен, и n каждый раз уменьшается, вы попадаете в базовый футляр, и вы можете это доказать.
Программисту нужно явно думать о базовом футляре и, возможно, о следующем слое (-ях) чуть выше базового случая. Рекурсивный Фибоначчи может быть лучшим примером, поскольку он сам вызывается дважды для каждого уровня рекурсии, .... return fib (n-1) + fib (n-2); – rcgldr
* Например, знаменитое предупреждение Кнута: «Я только доказал, что этот код правильный, не проверял его?» – Davislor
Но да, доказательство индукции имеет две части: доказательство базового случая и доказательство индукционного шага. Если вы также хотите доказать, что алгоритм завершается, вам нужно доказать, что некоторое количество из хорошо обоснованного набора приближается к базовому регистру с каждым шагом. В этом случае это * n *, уменьшающееся до 1. – Davislor
Для того, чтобы программист мог определить рекурсивную функцию, как правило, в некоторый момент времени до определения рекурсивной функции, программист обычно хотел бы понять, как работает рекурсия, но статья, похоже, сосредоточена на том, как определить рекурсивную в отличие от понимания того, как работает рекурсия, несмотря на название статьи. Так что, на мой взгляд, название статьи немного неверно.
Как уже отмечалось, для понимания рекурсии обычно используется простая рекурсивная функция в качестве примера обучения (factorial, Fibonacci, ...). Программисту не нужно прослеживать каждый уровень, но может рассмотреть, что происходит на нескольких уровнях чуть выше базового случая, а также в начальном случае и на одном или двух уровнях.
После того как рекурсия понята, тогда определение функции просто должно следовать правилам, упомянутым в статье.
Я думаю, что он говорит, что обычно вы не думаете о полной цепочке вызовов для рекурсивной функции (тем более, что она потенциально неограничена), а просто для базового случая и общего n-го шага (плюс, возможно, первый вызов, когда есть какая-то настройка). Я могу подтвердить, что редко я получаю какое-либо конкретное представление о рекурсивных проблемах, вступая в каждый вызов - хотя просмотр первых/последних нескольких кадров стека может помочь. –
@MatteoItalia: Если рекурсия не ограничена, там будут проблемы. –
Просто потому, что кто-то написал сообщение в блоге, в котором говорится, что X, Y или Z не делают этого. Если я напишу сообщение в блоге, в котором говорится: «Все должны послать Бобу миллион долларов», вы это сделаете? (*Пожалуйста скажи да!!!* :-). Лично я считаю, что отслеживание через пару примеров рекурсии - хороший способ показать, как и почему работают рекурсивные функции. Подумайте сами. –