Почему следующая рекурсивная программа дает следующий вывод - PullRequest
Новая
       29

Почему следующая рекурсивная программа дает следующий вывод

0 голосов
/ 01 марта 2020

Я пытаюсь понять рекурсию java с самого начала. Я прошел следующий пример 

public static void main(String[] args) {
  threeWays(1,4);
}

public static void threeWays(int id,int n) {
  if (n >= 0) {
    System.out.println(id + "=" + n);
    threeWays(id+1,n-1);
    threeWays(id+1,n-2);
  }
}

дает вывод 

1=4
2=3
3=2
4=1
5=0
4=0
3=1
4=0
2=2
3=1
4=0
3=0

Я понимаю до 5 = 0, но почему программа работает за пределами этого? Почему это не останавливается, когда n становится -1? Откуда берется 4 = 0? Я даже не знаю, как назвать это явление, поэтому вопрос может показаться расплывчатым. Любая помощь будет оценена.

1 Ответ

1 голос
/ 01 марта 2020 
threeWays(id+1,n-1); // when this returns,
threeWays(id+1,n-2); // ... the program still does this

Вы рекурсивно вызываете функцию дважды . Поэтому после того, как он достигает конца для первого вызова, он немного раскручивает стек, а затем переходит ко второй рекурсии.

И после этого второго вызова он снова дважды разветвляется на каждом уровне.

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

...