Как понять этот код рекурсии?

12

Я нашел этот код в руководстве, 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)

В руководстве не было ясно объяснено, что происходит на каждом этапе в этом примере кода, в частности, и я не мог понять, как здесь работает рекурсия. Можете ли вы помочь мне понять механику, шаг за шагом, что происходит в каждом случае?

докторская степень
источник
Я позволю кому-то другому помочь вам со словом «рекурсия» (потому что я думаю о нем как о чем-то ином, чем в данном контексте) или лучше объясню, что я собираюсь написать: (а) если число меньше или равно до 0, затем 0; (б) если число равно 1, то 1; (c) если число больше 1, то прибавьте число к значению, возвращаемому функцией, triangle-using-condс аргументом, который на 1 меньше любого числа. Условия идут в порядке a, b, а затем c - что бы ни совпадало сначала, это где доллар останавливается.
юрист
как обычно интерпретатор elisp оценивает от самого внутреннего до самого внешнего. Таким образом, 1-4 = 3. Теперь рекурсивный вызов будет (triangle-using-cond 3), но это будет заканчиваться тем же рекурсивным вызовом снова и снова, пока он не достигнет 1 условного, верно? что будет дальше?
докторская степень
О, я вижу - функция повторно использует себя на шаге 3 - хорошо, хороший момент.
юрист
Интересно, что будет в результате (triangle-using-cond 3)?
докторская степень
2
nb Функция 1-имеет особенно вводящее в заблуждение имя, особенно если вы читаете вызов, как если бы это была инфиксная запись. Возвращает аргумент минус один; НЕ один минус аргумент.
Фил

Ответы:

14

Использование «отладки printf»

Вы можете позволить Emacs помочь вам понять, изменив определение функции:

(defun triangle-using-cond (number)
  (message (format "called with %d" number))
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Просто добавьте (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с числом, меньшим или равным нулю.

Отсюда рекурсивный результат:

(+ number (+ (1- number) (+ (1- (1- number)) ... 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.

рекадо
источник
3
Edebug будет еще лучше. =)
Малабарба
Как распечатать след, используя message (...), C-x C-eпросто нажав показывает окончательный результат (10) больше ничего? Я что-то пропустил?
докторская степень
@ Малабарба, как привести Edebugв действие?
докторская степень
1
@doctorate ударил C-u C-M-xточку внутри функции, чтобы отладить его. Затем просто запустите функцию как обычно.
Малабарба
@ докторскую (message ...)материал печатает в *Message*буфер.
Рекадо
6

Модель замещения для применения процедуры из SICP может объяснить алгоритм для понимания кода, подобного этому.

Я написал некоторый код, чтобы облегчить это также. lispy-flattenиз lispy пакета делает это. Вот результат обращения lispy-flattenк (triangle-using-cond 4):

(cond ((<= 4 0)
       0)
      ((= 4 1)
       1)
      ((> 4 1)
       (+ 4 (triangle-using-cond (1- 4)))))

Вы можете упростить приведенное выше выражение просто:

(+ 4 (triangle-using-cond 3))

Затем сгладьте еще раз:

(+ 4 (cond ((<= 3 0)
            0)
           ((= 3 1)
            1)
           ((> 3 1)
            (+ 3 (triangle-using-cond (1- 3))))))

Конечный результат:

(+ 4 (+ 3 (+ 2 1)))
Або-або
источник
3

Это не относится к Emacs / Elisp, но если у вас есть математическое образование, то рекурсия подобна математической индукции . (Или, если вы этого не сделаете: тогда, когда вы изучаете индукцию, это похоже на рекурсию!)

Давайте начнем с определения:

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Когда 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)он вернет правильный ответ, и проверьте, будет ли он правильным в этом случае. Конечно, вы должны проверить базовый вариант тоже.

ShreevatsaR
источник
2

Шаги расчета для вашего примера будут выглядеть следующим образом:

(4 +               ;; step 1
   (3 +            ;; step 2
      (2 +         ;; step 3
         (1))))    ;; step 4
=> 10

Условие 0 фактически никогда не выполняется, потому что 1 как вход уже завершает рекурсию.

паприка
источник
(1)не является допустимым выражением.
Рекадо
1
Он оценивает просто отлично M-x calc. :-) Если серьезно, я хотел показать расчет, а не оценку Лиспа.
паприка
О, я даже не заметил, что это (4 +вместо (+ 4твоего ответа ... :)
rekado
0

Я думаю, что это довольно просто, вам не нужен 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

Теперь это очевидно.

чен бен
источник
Однако в случае этой функции f (0) никогда не вызывается.
Рекадо