Рекурсивный вызов одного и того же метода дважды

Question

В последовательности Фибоначчи я видел обычные реализации, которые рекурсивно вызывают один и тот же метод дважды:

public void fibonacci(int i)
{
fibonacci(1) + fibonacci(2);
}

Теперь этот метод не является точной копией того, что я видел, или правильным способом решения проблемы, но я видел два метода, добавленных вместе, как описано выше. Таким образом, метод вызывается не рекурсивно, а дважды. Что именно происходит при написании такого кода на C #? Два метода работают на отдельных потоках? Что происходит под капотом?

Answer 1

Нет, они называются один за другим. Дополнительные потоки не создаются, если вы явно не просите об этом (с помощью System.Threading). Я не уверен в порядке их вызова, но я бы предположил, что слева направо. В спецификации C # это определенно есть.

Answer 2

Это один из тех случаев, когда полезно подумать о том, как компьютер это делает.

Давайте начнем с функции. Я напишу его в псевдокоде со вкусом Python, потому что хочу, чтобы вы на секунду перестали думать о ЯЗЫКЕ.

def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    if n >  1: return fib(n-2) + fib(n-1)

Теперь давайте рассмотрим это для fib (2)

fib(2) имеет n> 1 , поэтому требуется третья ветвь,

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

поэтому он вызывает fib () с 0, что равно 0

   return 0 + fib(2-1)

звонки fib () с 1

   return 0 + 1

и мы видим результат 1. Теперь рассмотрим fib (3):

n> 1, поэтому

return fib(3-2)+fib(3-1)

и поскольку 3-2 равно 1, мы получаем fib (1) для первого члена, который равен 1:

return 1 + fib(3-1)

и теперь, когда мы вызываем fib (3-1), то есть fib (2), у нас пока нет прямого ответа; п> 1. Так становится

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

, который становится

    return 0 + 1

и мы возвращаемся к предыдущему звонку

return 1 + 1

и получите значение 2. Итак, вы видите, что нет отдельного потока, он просто работает через выражение. Я оставлю это в качестве упражнения, чтобы разработать пример для fib (4); Бьюсь об заклад, если вы это сделаете, однако, вы будете иметь это прибито.

Pop quiz: почему итеративная версия настолько значительно эффективнее?

Answer 3

В C # вы можете легко реализовать метод так, как вы предлагаете - он может выглядеть примерно так

public static int Fib(int i) {
   if (i == 0) return 0;
   if (i == 1) return 1;
   return Fib(i - 2) + Fib(i - 1);
}

Однако здесь нет магии. Это только один рекурсивный вызов, за которым следует другой. То есть весь код выполняется последовательно в одном потоке.

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

Answer 4

Они оцениваются последовательно. то есть fibonacci(1) оценивается до fibonacci(2). Если вы хотите визуализировать это, это случай спуска первого дерева вызовов (с его собственной «разделенной рекурсией»), обратно вверх, прежде чем идти вниз по вторым трем.

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