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

Попробуйте отладить и используйте часы, чтобы узнать состояние переменной

Хитрость в том, что первый вызов fibonacci () не возвращается, пока его вызовы fibonacci () не вернутся.

В итоге вы получаете вызов за вызовом fibonacci () в стеке, ни один из которых не возвращается, пока вы не дойдете до базового случая n == 0 || n == 1. В этот момент (потенциально огромный) стек вызовов fibonacci () начинает раскручиваться к первому вызову.

Как только вы осознаете это, это выглядит прекрасно, пока ваш стек не переполнится.

В случае кода 2, хотя n в конечном итоге достигнет точки, в которой он не удовлетворяет n> 0, и метод перестанет вызывать себя рекурсивно

, чтобы он выглядел похожим, вы можете заменить условие if (n == 0 || n == 1) с if (n <2)

Также я не вижу, как строка `возвращает fibonacci (n-1) + fibonacci (n-2) будет работать, поскольку fibbonacci n-2 должен в некотором смысле содержать fibonacci n-1, чтобы работать, но его еще нет.

Я подозреваю, что вы хотели написать: « поскольку фиббоначчи n-1 в каком-то смысле должны содержать фибоначчи n-2 »
Если я прав, то из приведенного ниже примера вы увидите, что на самом деле fibonacci (n-2) будет вызываться дважды для каждого уровня рекурсии ( fibonacci (1) в пример):
1. при выполнении fibonacci (n-2) на текущем шаге
2. при выполнении fibonacci ((n-1) -1) на следующем шаге

(Также обратите внимание на комментарий Спайка )

Предположим, вы вызываете fibonacci (3) , тогда стек вызовов для fibonacci будет таким:
(Вир предоставил более подробное объяснение ])

n=3. fibonacci(3)  
n=3. fibonacci(2) // call to fibonacci(n-1)
   n=2. fibonacci(1) // call to fibonacci(n-1)
      n=1. returns 1
   n=2. fibonacci(0) // call to fibonacci(n-2)
      n=0. returns 1
   n=2. add up, returns 2
n=3. fibonacci(1) //call to fibonacci(n-2)
   n=1. returns 1
n=3. add up, returns 2 + 1

Обратите внимание, что сложение в fibonacci (n) происходит только после возврата всех функций для меньших аргументов (т.е. fibonacci (n-1) , fibonacci (n-2) ... фибоначчи (2) , фибоначчи (1) , фибоначчи (0) )

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

public static String doIndent( int tabCount ){
    String one_tab = new String("   ");
    String result = new String("");
    for( int i=0; i < tabCount; ++i )
       result += one_tab;
    return result;
}

public static int fibonacci( int n, int recursion_level )
{
    String prefix = doIndent(recursion_level) + "n=" + n + ". ";

    if (n == 0 || n == 1){
        System.out.println( prefix + "bottommost level, returning 1" );
        return 1;
    }
    else{
        System.out.println( prefix + "left fibonacci(" + (n-1) + ")" );
        int n_1 = fibonacci( n-1, recursion_level + 1 );

        System.out.println( prefix + "right fibonacci(" + (n-2) + ")" );
        int n_2 = fibonacci( n-2, recursion_level + 1 );

        System.out.println( prefix + "returning " + (n_1 + n_2) );
        return n_1 + n_2;
    }
}

public static void main( String[] args )
{
    fibonacci(5, 0);
}

«Как вы можете использовать Фибоначчи, если вы еще не закончили объяснять, что это такое?»

Это интересный способ поставить под сомнение рекурсию. Вот часть ответа: пока вы определяете Фибоначчи, он еще не был определен , но был объявлен . Компилятор знает, что существует объект, называемый Фибоначчи, и что это будет функция типа int -> int и что она будет определяться при каждом запуске программы.

Фактически, именно так работают все идентификаторы в программах на языке C, а не только рекурсивные. Компилятор определяет, что было объявлено, и затем просматривает программу, указывающую на использование этих вещей там, где они находятся на самом деле (грубое упрощение).

Для понимания рекурсии необходимо также знать, как работает стек вызовов, то есть как функции вызывают друг друга.
Если бы функция не имела условия для остановки, если n == 0 или n == 1, тогда функция вызывала бы себя рекурсивно навсегда. Это работает, потому что в конечном итоге функция собирается замкнуться и вернуть 1. в этот момент return fibonacci (n-1) + fibonacci (n-2) также вернется со значением, и стек вызовов будет очищен очень быстро.

Позвольте мне пройтись по выполнению, учитывая n=3. Надеюсь, это поможет.

При n=3 => условие if не выполняется и выполняется else

return fibonacci (2) + fibonacci (1);  

Разделите утверждение:

1. Найти значение fibonacci(2)
2. Найти значение fibonacci(1)
   // Обратите внимание, что это не fib(n-2) и оно не будет требовать fib(n-1) для своего выполнения. Оно является независимым. Это относится и к шагу 1.
3. Складываем оба значения
4. возвращаем суммированное значение

Способ выполнения (Расширяя вышеприведенные четыре шага):

1. Находим значение fibonacci(2)

   1. if fails, else executes
   2. fibonacci(1)
      1. if executes
      2. значение '1' возвращается на шаг 1.2. и управление переходит на шаг 1.3.
   3. fibonacci(0)
      1. if executes
      2. значение '1' возвращается на шаг 1.3. и управление переходит на шаг 1.4.
   4. Добавьте оба варианта
      1. sum=1+1=2 //из шагов 1.2.2. и 1.3.2.
   5. return sum //значение '2' возвращается на шаг 1. и управление переходит на шаг 2
      

2. Найти значение fibonacci(1)

   1. if executes
   2. возвращается значение '1'

3. Сложить оба значения

   1. sum=2+1 //из шагов 1.5. и 2.2.
4. возвращает суммированное значение //sum=3

Я объясню, что делает ваш компьютер при выполнении этого куска кода на примере:

Представьте, что вы стоите в очень большой комнате. В комнате рядом с этой комнатой у вас есть огромное количество бумаги, ручек и столов. Теперь мы собираемся вычислить число Фибоначчи(3):

Мы берем стол и ставим его где-нибудь в комнате. На стол кладем бумагу и пишем на ней "n=3". Затем мы задаем себе вопрос: "Хм, а 3 равно 0 или 1?". Ответ - нет, поэтому мы сделаем "return fibonacci (n-1) + fibonacci (n-2);".

Однако есть проблема: мы понятия не имеем, что на самом деле делают "fibonacci (n-1)" и "fibonacci (n-2)". Поэтому мы берем еще две таблицы и размещаем их слева и справа от нашей первоначальной таблицы с надписями на обеих: "n=2" и "n=1".

Мы начинаем с левой таблицы и задаемся вопросом: "2 равно 0 или 1?". Конечно, ответ отрицательный, поэтому мы снова поставим рядом с этим столом две таблицы с надписями "n=1" и "n=0".

Все еще следите? Вот как выглядит комната:

n=1

n=2 n=3 n=1

n=0

Начнем с таблицы с "n=1", и эй, 1 равно 1, так что мы действительно можем вернуть что-то полезное! Мы пишем "1" на другой бумажке и возвращаемся к таблице с "n=2". Мы кладем бумажку на стол и идем к другой таблице, потому что мы все еще не знаем, что будем делать с этой другой таблицей.

"n=0", конечно, тоже возвращает 1, поэтому мы пишем это на бумажке, возвращаемся к таблице n=2 и кладем бумажку туда. В этот момент на этом столе есть две бумажки с возвращаемыми значениями таблиц с "n=1" и "n=0", поэтому мы можем вычислить, что результат вызова этого метода на самом деле равен 2, поэтому мы пишем это на бумажке и кладем ее на стол с "n=3".

Затем мы переходим к таблице с "n=1", расположенной справа, и можем сразу же написать 1 на бумажке и положить ее обратно на таблицу с "n=3". После этого у нас, наконец, достаточно информации, чтобы сказать, что fibonacci(3) возвращает 3.

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

    public static int NotUseful()
    {
        return NotUseful();
    }

будет просто бесконечно циклиться, или, как в моем примере, вы будете продолжать размещать все больше и больше таблиц, не получая ничего полезного. Вашему компилятору все равно, что на самом деле делают fibonacci(n-1) или fibonacci(n-2).

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