Я нашел этот код в руководстве, An Introduction to Programming in Emacs Lisp
демонстрирующем рекурсию с помощью cond
функции, чтобы узнать количество камешков на основе введенного количества строк, то есть, если строк = 2, то галька должна быть 3, если 4 строки, то это должно быть 10 галька там.
(defun triangle-using-cond (number)
(cond ((<= number 0) 0)
((= number 1) 1)
((> number 1)
(+ number (triangle-using-cond (1- number))))))
оцените до 10 после передачи аргумента 4:
(triangle-using-cond 4)
В руководстве не было ясно объяснено, что происходит на каждом этапе в этом примере кода, в частности, и я не мог понять, как здесь работает рекурсия. Можете ли вы помочь мне понять механику, шаг за шагом, что происходит в каждом случае?
triangle-using-cond
с аргументом, который на 1 меньше любого числа. Условия идут в порядке a, b, а затем c - что бы ни совпадало сначала, это где доллар останавливается.1-4 = 3
. Теперь рекурсивный вызов будет(triangle-using-cond 3)
, но это будет заканчиваться тем же рекурсивным вызовом снова и снова, пока он не достигнет 1 условного, верно? что будет дальше?(triangle-using-cond 3)
?1-
имеет особенно вводящее в заблуждение имя, особенно если вы читаете вызов, как если бы это была инфиксная запись. Возвращает аргумент минус один; НЕ один минус аргумент.Ответы:
Использование «отладки printf»
Вы можете позволить Emacs помочь вам понять, изменив определение функции:
Просто добавьте
(message ...)
куда-нибудь, чтобы в*Messages*
буфер был напечатан след .Используя Edebug
Поместите точку в любое место внутри определения функции и нажмите
C-u C-M-x
«инструмент». Затем оцените функцию, например, поставив точку после(triangle-using-cond 3)
и нажавC-x C-e
.Теперь вы находитесь в режиме Edebug. Нажмите пробел, чтобы пройти через функцию. Промежуточные значения каждого выражения отображаются в области эха. Для выхода из режима Edebug просто нажмите
q
. Чтобы удалить инструментарий, поместите точку в любом месте определения и нажмите,C-M-x
чтобы переоценить определение.Использование стандартного отладчика Emacs
M-x debug-on-entry triangle-using-cond
затем, когдаtriangle-using-cond
вызывается, вы помещаетесь в отладчик Emacs (буфер*Backtrace*
).Пройдите оценку, используя
d
(илиc
пропустите любые неинтересные оценки).Чтобы увидеть промежуточное состояние (значения переменных и т. Д.), Вы можете использовать в
e
любое время. Вам будет предложено ввести sexp для оценки, и результат оценки будет напечатан.Пока вы используете отладчик, держите копию исходного кода видимой в другом фрейме, чтобы вы могли следить за тем, что происходит.
Вы также можете вставить явные вызовы для входа в отладчик (более или менее точек останова) в произвольных местах исходного кода. Вы вставляете
(debug)
или(debug nil SOME-SEXP-TO-EVALUATE)
. В последнем случае при вводе отладчикаSOME-SEXP-TO-EVALUATE
выполняется оценка и выводится результат. (Помните, что вы можете вставить такой код в исходный код и использовать егоC-M-x
для оценки, а затем отменить - вам не нужно сохранять отредактированный файл.)См. Руководство Elisp, узел
Using Debugger
для получения дополнительной информации.Рекурсия как петля
Во всяком случае, думать о рекурсии как о петле. Определены два случая прекращения:
(<= number 0)
и(= number 1)
. В этих случаях функция возвращает простое число.В рекурсивном случае функция возвращает сумму этого числа и результат функции с
number - 1
. В конце концов, функция будет вызываться либо1
с числом, меньшим или равным нулю.Отсюда рекурсивный результат:
Взять к примеру
(triangle-using-cond 4)
. Давайте накопим окончательное выражение:в первой итерации
number
есть4
, так что(> number 1)
ветка следует. Мы начинаем строить выражения(+ 4 ...
и вызвать функцию с(1- 4)
, то есть(triangle-using-cond 3)
.сейчас
number
есть3
, и результат есть(+ 3 (triangle-using-cond 2))
. Общее выражение результата(+ 4 (+ 3 (triangle-using-cond 2)))
.number
является в2
настоящее время, так что выражение(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))
number
в1
настоящее время, и мы берем(= number 1)
ветвь, в результате раздражения1
. Целое выражение есть(+ 4 (+ 3 (+ 2 1)))
. Оценивать , что изнутри , и вы получите:(+ 4 (+ 3 3))
,(+ 4 6)
или просто10
.источник
message (...)
,C-x C-e
просто нажав показывает окончательный результат (10) больше ничего? Я что-то пропустил?Edebug
в действие?C-u C-M-x
точку внутри функции, чтобы отладить его. Затем просто запустите функцию как обычно.(message ...)
материал печатает в*Message*
буфер.Модель замещения для применения процедуры из SICP может объяснить алгоритм для понимания кода, подобного этому.
Я написал некоторый код, чтобы облегчить это также.
lispy-flatten
из lispy пакета делает это. Вот результат обращенияlispy-flatten
к(triangle-using-cond 4)
:Вы можете упростить приведенное выше выражение просто:
Затем сгладьте еще раз:
Конечный результат:
источник
Это не относится к Emacs / Elisp, но если у вас есть математическое образование, то рекурсия подобна математической индукции . (Или, если вы этого не сделаете: тогда, когда вы изучаете индукцию, это похоже на рекурсию!)
Давайте начнем с определения:
Когда
number
есть4
, ни одно из первых двух условий не выполняется, поэтому оно оценивается согласно третьему условию:(triangle-using-cond 4)
оценивается как(+ number (triangle-using-cond (1- number)))
, а именно как(+ 4 (triangle-using-cond 3))
.Точно так же
(triangle-using-cond 3)
оценивается как(+ 3 (triangle-using-cond 2))
.Точно так же
(triangle-using-cond 2)
оценивается как(+ 2 (triangle-using-cond 1))
.Но ведь
(triangle-using-cond 1)
второе условие выполняется, и оно оценивается как1
.Совет для тех, кто изучает рекурсию: старайтесь избегать
Если вы пытаетесь убедить себя, вернете ли
(triangle-using-cond 4)
вы правильный ответ, просто предположите, что(triangle-using-cond 3)
он вернет правильный ответ, и проверьте, будет ли он правильным в этом случае. Конечно, вы должны проверить базовый вариант тоже.источник
Шаги расчета для вашего примера будут выглядеть следующим образом:
Условие 0 фактически никогда не выполняется, потому что 1 как вход уже завершает рекурсию.
источник
(1)
не является допустимым выражением.M-x calc
. :-) Если серьезно, я хотел показать расчет, а не оценку Лиспа.(4 +
вместо(+ 4
твоего ответа ... :)Я думаю, что это довольно просто, вам не нужен emacs lisp, это просто математика для начальной школы.
f (0) = 0
f (1) = 1
f (n) = f (n-1) + n при n> 1
поэтому f (5) = 5 + f (4) = 5 + 4 + f (3) = 5 + 4 + 3 + 2 + 1 + 0
Теперь это очевидно.
источник