Как вычисляется x * func(x, n — 1) (рекурсия)?

Question

[Марик Цукор]

Почти не понимаю, как происходит рекурсия, сколько не читаю материал, все так абстрактно и не совсем "логично".

function func(x, n) {
  if (n != 1) { 
    return x * func(x, n - 1);
  } else {
    return x;
  }
}

alert(func(4, 3));

Вот почему этот код возвращает 64? это ведь не цикл! проверка должна идти один раз if (n != 1), но тут почему-то по другому. Но это ладно. Каким образом происходит вычисление выражения x * func(x, n - 1) ? Ведь если подставить 4 и 3, то получится 4 * func(4, 3 - 1). А это в свою очередь 4 * func(4, 2). И вот каким образом происходит умножение 4 на func(4,2)? что на что умножается? что возвращает функция до умножения и почему это так происходит? Спасибо за понимание! Надеюсь, я это пойму

Answer 1

[timfcsm]

первый проход : 3!=1 => 4 * (func(4, 3-1))
второй проход: 2!=1 => 4 * (func(4, 1))
третий проход: 1==1 => возвращаем 4
во втором проходе подставляем 4 => 4*4 = 16, возвращаем 16
в первом проходе подставляем 16 => 4 * 16 = 64

Comments

[Марик Цукор]

как описать такое поведение? 4 * (func(4, 2)). В этом же выражении 4 умножается на 4, но почему на 4, а не на 2? ведь оператор запятая вычисляет первое значение, потом второе, и возвращает второе, а тут наоборот. Поясните пожалуйста этот момент. Это наверное самая большая причина, по которой мне непонятно почему это действует. ни разу не перемножал значение на функцию

[timfcsm]

там нет оператора запятой, это разделитель, там вызов функции func(4, 2), а 4 и 2 это соответственно параметры x и n.
оператор запятая был бы в таком случае 4 * (4, 2)

[Марик Цукор]

timfcsm: да, но каким образом 4 перемножается на себя? оно же перемножает первый параметр x? тогда все сходится

[timfcsm]

BeriaFantom: 4 перемножается на результат вызова функции,
func(4, 2-1) == func(4, 1) == 4.
func(4, 3-1) == func(4, 2) == (4 * func(4, 2-1)) == (4 * func(4, 1)) == 4 * 4
func(4, 3) == (4 * func(4, 3-1)) == (4 * func(4, 2)) == (4 * (4 * func(4, 2-1))) == ( 4 * (4 * func(4, 1))) == 4 * 4 * 4 == 64

[Марик Цукор]

timfcsm: спасибо, понял) т.е например func(15,1) == 15 ?

[timfcsm]

BeriaFantom: ну да , в n != 1 мы не попадаем, значит вернет 15

Answer 2

[Михаил Белошицкий]

Для понимания рекурсии, нужно понимать модель вычисления - то есть, что куда подставляется транслятором Js и в каком порядке. После этого все будет достаточно несложно - нужно лишь действовать как на уроках математики - просто подставляйте числа на места переменных, а тело функции на место ее вызова и упрощайте то, что можно упростить до того момента, когда упрощать станет нечего.

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

Comments

[Марик Цукор]

спасибо, debugger еще хорошо помог разобраться

Answer 3

[Даниил Игоревич]

Есть стек контекстов, который запоминает значения. Если не ошибаюсь, то ваша функция работает так:
1) Вызывается func(4,3)
n != 1, поэтому возвращается 4 * func(4, 2) (Запоминается в стеке контекстов)
2) Вызывается func(4,2)
n != 1, поэтому возвращается 4 * func(4,1) (Запоминается в стеке контекстов)
3) Вызывается func(4,1)
n === 1, поэтому возвращается x, то есть 4, и дальше срабатывает то, что запомнилось в стеке контекстов:
2) 4 * func(4,1), где func(4,1) = 4, поэтому 4 * 4 = 16
1) 4 * func(4,2), где func(4,2) = 16, поэтому 4 * 16 = 64
Кстати, про рекурсию
И закрепить

Answer 4

[Аскар Мухаметшин]

Разбиваем по шагам (для понимания работы рекурсии на машине нужно принимать во внимание работу стеков вызовов):

1. [уровень стека 0] Вызов func(4, 3)
   
2. [уровень стека 1] n == 1 ? Нет
   
3. [уровень стека 1] Вызов func(4, 2)
   
4. [уровень стека 2] n == 1 ? Нет
   
5. [уровень стека 2] Вызов func(4, 1)
   
6. [уровень стека 3] n == 1 ? Да
   
7. [уровень стека 3] Возвращаем значение Х равное 4
   
8. [уровень стека 2] Возвращаем значение выражения Х, умноженное на возвращенное значение (4 * 4), равное 16
   
9. [уровень стека 1] Возвращаем значение выражения Х, умноженное на возвращенное значение (4 * 16), равное 64
   
10. [уровень стека 0] Получаем 64