Рекурсивное умножение в схеме (положительные числа)

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

;Recursive Arithmetic
(define increment
  (lambda (x)
    (+ x 1)))

(define decrement
  (lambda (x)
    (- x 1)))

(define recursive-add
  (lambda (x y)
    (if (zero? y)
        x
        (recursive-add (increment x) (decrement y)))))

"Define Multiplication Recursively"
(define recursive-mult
  (lambda (x y)
    (if (zero? y)
        0
        (recursive-add x (recursive-mult x (decrement y)))))) ;else

(recursive-mult 9 5)

Мое первое сомнение заключается в том, какая часть раздела else выполняется первой?

В разделе else, если (decrement y) выполняется первым, то y сначала уменьшается на 1, затем выполняется раздел (recursive-mult x, по которому функция вызывает сама себя, поэтому раздел (recursive-add x никогда не вызывается в той же строке кода.

Теперь, если в разделе else сначала выполняется recursive-add x, сначала добавляется x, затем запускается recursive-mult x, который снова запускает всю функцию, а (decrement y) никогда не достигается.

Теперь я знаю одно из двух моих предположений выше, или, может быть, оба они неверны. Может ли кто-нибудь указать мне правильное направление, пожалуйста? Я извиняюсь, если мой вопрос показывает высокий уровень неадекватности в этой теме, но я действительно хочу выучить схему как следует. Спасибо.

Как вы думаете, почему recursive-mult никогда не вернется? Рекурсивные функции работают точно так же, как нерекурсивные функции; их аргументы оцениваются до того, как они будут вызваны, и они возвращаются в то место, откуда их вызвали.

molbdnilo 16.01.2023 08:41

Возможно, ваше представление о том, что (recursive-add x и (recursive-mult x являются отдельными «разделами», является частью недоразумения. (recursive-mult x (decrement y)) то же самое, что и (recursive-mult x (- y 1)), и является одним неделимым выражением. Например, (recursive-mult 3 2) обратится к (recursive-add 3 (recursive-mult 3 1)).

molbdnilo 16.01.2023 13:52
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
2
2
62
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Это ответ на Common Lisp, с которым я более знаком, но подход тот же. Вот перевод вашего кода:

(defpackage :so (:use :cl))
(in-package :so)

(defun add (x y)
  (if (zerop y)
      x
      (add (1+ x) (1- y))))

(defun mul (x y)
  (if (zerop y)
      0
      (add x (mul x (1- y)))))

Функции increment и decrement не определены, я использую 1+ и 1-, которые эквивалентны.

В разделе else, если (декремент y) выполняется первым, то y сначала уменьшается на 1, затем выполняется раздел (recursive-mult x), по которому функция вызывает сама себя, поэтому раздел (recursive-add x никогда не вызывается в эта же строка кода.

Вы можете использовать модель подстановки для оценки рекурсивных функций.

(add (add 1 3) 1)

Давайте сначала оценим первый аргумент самого верхнего and:

(add (add 2 2) 1)
(add (add 3 1) 1)
(add (add 4 0) 1)
(add 4 1)

Здесь вызов в конечном итоге возвращается, и первый аргумент равен 4. После возобновления выполнения выполняется остальная часть кода для (add (add 1 3) 1), что эквивалентно:

(add 5 0)

И наконец:

5

Каждый раз, когда вы вызываете функцию, в стек вызовов помещается новый кадр, что и показано в трассировке:

(trace mul add)

Приведенный выше макрос в Common Lisp делает так, чтобы функции mul и add трассировались. Теперь, когда я запускаю программу, при входе и выходе печатается трассировка. Попробуем с небольшими значениями:

(mul 2 3)

Трассировка выводится следующим образом (не обращайте внимания на префикс SO::, это часть полного имени символов):

  0: (SO::MUL 2 3)
    1: (SO::MUL 2 2)
      2: (SO::MUL 2 1)
        3: (SO::MUL 2 0)
        3: MUL returned 0
        3: (SO::ADD 2 0)
        3: ADD returned 2
      2: MUL returned 2
      2: (SO::ADD 2 2)
        3: (SO::ADD 3 1)
          4: (SO::ADD 4 0)
          4: ADD returned 4
        3: ADD returned 4
      2: ADD returned 4
    1: MUL returned 4
    1: (SO::ADD 2 4)
      2: (SO::ADD 3 3)
        3: (SO::ADD 4 2)
          4: (SO::ADD 5 1)
            5: (SO::ADD 6 0)
            5: ADD returned 6
          4: ADD returned 6
        3: ADD returned 6
      2: ADD returned 6
    1: ADD returned 6
  0: MUL returned 6

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

Схема имеет нетерпеливую оценку, поэтому, если у вас есть

(op1 expr1 (op2 1 (op3 expr2 expr3)))

Тогда форма op1 будет зависеть от expr1, а форма с op2 должна быть завершена, прежде чем можно будет применить op1. Если у нас есть реализация, которая выполняет оценку слева направо, он будет делать это следующим образом:

(let ((vexpr1 expr1)
      (vexpr2 expr2)
      (vexpr3 expr3))
  (let ((vop3 (op3 vexpr2 vexpr3)))
    (let ((vop2 (op2 1 vop3)))
      (op1 vexpr1 vop2))))

  

Итак, чтобы ответить на ваш вопрос, порядок на той же схеме слева направо будет:

(let ((vdy (decrement y)))
  (let ((vrm (recursive-mult x vdy)))
    (recursive-add x vrm)))

То же самое в ЦПС:

(decrement& y 
            (lambda (vdy)
              (recursive-mult& x 
                               vy 
                               (lambda (vrm)
                                 (recursive-add& x vrm continuation)))))

Таким образом, на практике приложение для первого раунда не происходит до того, как все recursive-mult для меньшего выражения произойдет первым. Таким образом (recursive-mult 3 3) превращается в

(recursive-add 3 (recursive-add 3 (recursive-add 3 0)))

И, как вы можете видеть, сначала выполняется последнее, затем второе и последнее сложение, которое нужно выполнить, — это одно из первого раунда перед рекурсией.

Другие вопросы по теме