Как работает данная рекурсия?

Question

[incentive]

function paw(res, num) {
  if (num === 1) {
    return res;
  } else {
    return res * paw(res, num - 1);
  }
}
var result = paw(2, 5);
console.log(result);

Вот значит, num не равен 1, переходим дальше.
res = 2
num = 5.
Теперь идет поочередный запуск функции в которой из num вычитается 1. Когда num становится 1, срабатывает наш if который возвращает уже готовый результат.
Но как происходит перемножение? Растолкуйте пожалуйста

Comments

[Lynn «Кофеман»]

В пятой строчке есть знак умножения. Вот там оно и происходит

[longclaps]

Алексей Тен, не где, но как?!

[incentive]

Алексей Тен, 2 *paw( 2, 5-1);
Как срабатывает умножение именно res на res?
Как и куда передаются уже перемноженные res?

[longclaps]

buchecha, уже перемноженные res передаются в return, а далее - по месту вызова.

[Rustam Azizov]

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

[Lynn «Кофеман»]

longclaps, столбиком очевидно. Компьютеры по другому не умеют умножать же.

buchecha, Где у вас умножение res на res? Тут умножение res на результат вызова функции paw(2, 4).

[longclaps]

столбиком очевидно.

Алексей Тен, тут ты совсем не прав. Там и близко не столбик, а что - неизвестно. Но идеи Карацубы там цветут и пахнут.

[Lynn «Кофеман»]

longclaps, про столбик это была шутка :)

Answer 1

[Rustam Azizov]

paw(2, 5) = 2 * paw(2, 4)
2 * paw(2, 4)                   --> paw(2, 4) = 2 * paw(2, 3)
2 * (2 * paw(2, 3))             --> paw(2, 3) = 2 * paw(2, 2)
2 * (2 * (2 * paw(2, 2)))       --> paw(2, 2) = 2 * paw(2, 1)
2 * (2 * (2 * (2 * paw(2, 1)))) --> paw(2 ,1) = 2
2 * (2 * (2 * (2 * 2)))

На 3 строчке не готовый результат, а просто значение res и оно просто подставляется вместо рекурсивного вызова функции на пятой.

Comments

[incentive]

Мне препод примерно такое же нарисовал.
Я не понимаю от куда столько 2*( берутся
Голова кипит
Я понимаю почему данная функция работает, но не могу сообразить как там под капотом. В голове нарисовать весь этот цикл .

[Rustam Azizov]

Всё просто, сморите в вызов функции, находите ту часть которая будет вызвана и подставляете этот кусок кода вместо самой функции. Если у вас paw(2, 1), то if (num === 1) даст true и вернёт res. То есть paw(2, 1) можно заменить просто на 2. В остальных случаях надо подставлять на строчку после else — пятую строчку. Она равна res * paw(res, num - 1). В нашем случае мы начинаем с paw(2, 5) и заменяем её на пятую строчку где получится 2 * paw(2, 4) и так до тех пор, пока у нас не останется ни одного вызова paw. А только числа и операторы умножения.

[incentive]

Rustam Azizov, только хотел писать,что вроде понял
на моем языке
сработал else 2 * (2, 4)
снова срабатывает else 2 * на функцию, но она после первого else выглядит так - 2 * paw (2, 4), а не так paw (2, 4).
Надеюсь правильно осознал)
спасибо!

[longclaps]

buchecha, хватит уже. Нахрена тебе пятая степень? Разрисуй вторую, там уже есть вложенность. Знаешь, что такое стек? Не знаещь - вон Rustam Azizov тебе растолкует.

[Rustam Azizov]

longclaps, я думаю он понял.

[Rustam Azizov]

buchecha, Всё верно. Раз помогло, то не пожалейте пометить как ответ.

[longclaps]

Rustam Azizov, ничего, лишним не будет. Эти знания навсегда, и мир уже не будет прежним )

[incentive]

Rustam Azizov, Можно еще вопрос пожалуйста.
После того как срабатывает if и он ретурнит 2, как срабатывает else вот с этими функцями? 2 * (2 * (2 * (2 * paw(2, 1)))) .
Или они в конце поочередно завершаются тем самым вычисляя результат?

upd. А вроде догнал, if же запускается во вложенной , а не главной

Answer 2

[McBernar]

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

Все вычисления начинаются только тогда, когда рекурсия достигнет конца и вернет res.

Вот картинка под ваш пример. Обратите внимание на зеленые прямоугольники.