Как работает рекурсия, когда в одном операторе есть два рекурсивных вызова?

Question

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

Но я не понимаю, как работает рекурсия, когда в выражении типа f (n) + f (n / 2) есть два рекурсивных вызова.Я имею в виду, какой вызов разрешается первым, а когда - второй.Также как рассчитывается сумма, если это выражение присваивается выписке?Я написал небольшой код, чтобы расшифровать это сам.

#include <iostream>
#include <string>


int main()
{
  int recursionTest(int n, char c);
  int x;
  std::cin>>x;
  std::cout<<"Ans:"<<recursionTest(x,'c');

}


int recursionTest(int n,char c)
{
   int result=0;
   if(n==0)
    return 1;
   std::cout<<n<<":"<<c<<std::endl;
   result=recursionTest(n/2,'L')+recursionTest(n/3,'R');////I cant figure 
                                                           out the flow of 
                                                           control here!!!
   return result;
}

И я получил следующий вывод.

24
24:c
12:L
6:L
3:L
1:L
1:R
2:R
1:L
4:R
2:L
1:L
1:R
8:R
4:L
2:L
1:L
1:R
2:R
1:L
Ans:20

ТАК, я понял, это древовидная структура.Но я все еще не знаю, как мы получаем 20 в качестве ответа (input = 24).Как работает выражение суммы и что оно суммирует, как я могу посмотреть на древовидную структуру и сгенерировать ее?

Answer 1

Здесь оператор приоритета будет играть роль

f(n) + f(n/2);

В приведенном выше фрагменте кода сначала вызывается фрагмент f (n), а затем f (n / 2).в основном арифметические операторы компилируются слева направо.Если вы хотите отладить код, используйте операторы printf внутри функции f (int), печатая значение n.Таким образом вы можете получить код

Answer 2

Не существует определенного порядка для того, как оцениваются два подвыражения оператора +.Компилятор может генерировать код для оценки одного первого, а другого второго.Он может даже чередовать некоторые вычисления одной стороны с вычислениями другой.Например, он может вычислить n/3, затем n/2, затем правый вызов функции и, наконец, левый вызов функции.

Управление потоком аналогично одному случаю рекурсии, за которым следует еще одиндело.Итак, ваша строка:

result=recursionTest(n/2,'L')+recursionTest(n/3,'R');

фактически совпадает с:

int left = recursionTest(n/2,'L');
int right = recursionTest(n/3,'R');
result = left + right;

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