Является ли эта хвостовая рекурсия?

Question

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

public static long fib(long index) { 

// assume index >= 0 

if (index == 0) // Base case 

    return 0; 

else 

    if (index == 1) // Base case 

    return 1; 

    else 

    // Reduction and recursive calls 

    return fib(index - 1) + fib(index - 2); 

} // end of method fib(long index) 

Answer 1

Нет, метод в вопросе не использует хвостовую рекурсию. Рекурсия хвоста легко распознается: рекурсивным шагом является последнее вещь, которая происходит в методе.

В вашем коде после оба рекурсивных вызова завершаются, есть еще одна операция - дополнение. Таким образом, метод рекурсивный, но не хвостовой рекурсивный.

Для сравнения, здесь приведена рекурсивная реализация метода fib() - обратите внимание на то, как нам нужно передать дополнительные параметры для сохранения состояния рекурсии и, что более важно, заметить, что после операции не осталось никаких операций рекурсивный вызов.

public static long fib(int n, long a, long b) { 
    return n == 0 ? b : fib(n-1, a+b, a); 
} 

Используйте это так:

fib(10, 1, 0) // calculates the fibonacci of n=10 
=> 55 

предыдущей реализации будет работать нормально до п = 92, для больших чисел вы должны будете использовать BigInteger вместо long, и лучше переключиться на итерационный алгоритм.

Answer 2

@ Óscar López ответил на вопрос.

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

Однако, поскольку вы отметили вопрос с помощью java, вы должны знать, что текущие реализации Java НЕ реализуют оптимизацию хвостового вызова. Вызов с глубоким рекурсивным методом в Java может привести к ошибке StackOverflowError.