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

Код 1:

public static int fibonacci (int n){ 
    if (n == 0 || n == 1) { 
        return 1; 
    } else { 
        return fibonacci (n-1) + fibonacci (n-2); 
    }        
}

Как вы можете использовать fibonacci, если вы еще не закончили объяснять, что это такое? Я мог понять, используя рекурсию в других случаях:

Код 2:

class two 
{
    public static void two (int n) 
    {
        if (n>0) 
        {
            System.out.println (n) ;
            two (n-1) ;
        }
        else
        {
            return ;
        }
    } 

    public static void main (String[] arg) 
    {
        two (12) ;
    }
}

В случае кода 2, однако, n в конечном итоге достигнет точки, в которой она не удовлетворяет n>0, и метод перестанет называть себя рекурсивно. В случае кода 2, однако, я не вижу, как он сможет получить себя от 1, если n=1 был отправной точкой для 2 и 3 и 5 и так далее. Кроме того, я не вижу, как работает строка return fibonacci (n-1) + fibonacci (n-2), поскольку fibonacci (n-2) должна содержать в некотором смысле fibonacci (n-1) для работы, но ее пока нет.

Книга, на которую я смотрю, говорит, что она сработает. Как это работает?

Ответ 1

Хорошо, отложив в сторону то, что на самом деле делает компилятор для вашего кода (это ужасно, но красиво), и как процессор на самом деле интерпретирует ваш код (аналогично), существует довольно простое решение.

Рассмотрим следующие текстовые инструкции:

Для сортировки нумерованных блоков:

выберите случайный блок.
если это единственный блок, остановитесь.
перемещать блоки с меньшими номерами влево, более высокие цифры справа.
сортировать блоки с более низким номером.
сортировать блоки с более высоким номером.

Когда вы дойдете до инструкций 4 и 5, вас попросят снова начать весь процесс. Однако это не проблема, потому что вы все еще знаете, как запустить этот процесс, и когда все это закончится, у вас есть куча отсортированных блоков. Вы могли бы покрыть инструкции с помощью листов бумаги, и им не было бы труднее следовать.

Ответ 2

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

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

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

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

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

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

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)... fibonacci (2), fibonacci (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);
}

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Когда n = 3 = > если условие терпит неудачу, а else выполняет

return fibonacci (2) + fibonacci (1);

Разделите оператор:

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

Как он выполняется (Развертывание выше четырех шагов):

Найдите значение фибоначчи (2)
- если сбой, else выполняет
- Фибоначчи (1)
  - если выполняется
  - Значение '1' возвращается к шагу 1.2. и управление переходит к этапу 1.3.
- Фибоначчи (0)
  - если выполняется
  - Значение '1' возвращается к шагу 1.3. и управление переходит к этапу 1.4.
- Добавьте оба
  - sum = 1 + 1 = 2//из шагов 1.2.2. и 1.3.2.
- return sum//значение '2' возвращается на шаг 1. и элемент управления переходит к шагу 2
Найдите значение фибоначчи (1)
- если выполняется Возвращается
- значение '1'
Добавьте оба значения
- sum = 2 + 1//из шагов 1.5. и 2.2.
возвращает суммированное значение //sum = 3

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

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

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

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

По-прежнему следует? Это выглядит так:

п = 1

n = 2 n = 3 n = 1

п = 0

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

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

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

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

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

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