как отследить рекурсивную функцию C ++

Question

#include <iostream>
using namespace std;

int g(float A[] , int L , int H)
{
   if (L==H)
      if (A[L] > 0.0)
         return 1;
      else 
         return 0;
   int M = (L+H)/2;

   return g(A,L,M)+ g(A,M+1,H);
}
int main (void)
{       
   float A[] = {-1.5 ,3.1,-5.2,0.0};
   g(A,0,3);

   system ("pause");
   return 0;
}

спрашивает меня, что возвращает функция g и что делает функция

вот что я получил до сих пор

первый звонок (А, 0, 3) Итого пропустить оператор IF и M = 1, так как это int -обрат, г (А, 1,3) + г (А, 2 3)

второй звонок - снова g (A, 1,3) - М = 0; - g (A, 2 3) пропустить оператор if снова - М = 2;

третий звонок -г (А, 0,0,) вернуть 0 -g (А, 3,3) возврат 0;

так что просто вернуть 0?

и я предполагаю, что это делит среднее значение и какой-то бинарный поиск?

Answer 1

Это сложный способ подсчитать, сколько чисел в массиве больше 0. И если вы попытаетесь запустить это в компиляторе, возвращаемое значение будет 1, потому что единственное число, которое больше 0 в массиве, это 3.1 .

при первом запуске:

{-1.5, 3.1, -5.2, 0.0}
   0    1     2    3
   L               H

затем, начиная с L=0 и H=3, M = (0+3)/2 = 3/2 = 1, когда вы достигаете g(A, L, M) + g(A, M+1, H), вы разветвляетесь на две части:

{-1.5, 3.1, -5.2, 0.0}
   0    1     2    3
   L               H
   L1   H1    L2   H2

давайте сначала сделаем левую часть g(A, L1, H1) = g(A, 0, 1):

{-1.5, 3.1, -5.2, 0.0}
   0    1     2    3
   L               H
   L1   H1    L2   H2
   ^^^^^^^

снова с L1=0, H1=1 и т. Д. M1 = (0+1)/2 = 1/2 = 0 и вы снова разветвляетесь на две части g(A, 0, 0) и g(A, 1, 1):

{-1.5,    3.1,    -5.2, 0.0}
   0       1        2    3
   L               H
   L1      H1      L2    H2
L11,H11 L12,H12

в левой части, начиная с -1.5 <= 0, следовательно, g(A, L11, H11) = g(A, 0, 0) = 0, в правой части, начиная с 3.1 > 0, следовательно, g(A, L12, H12) = g(A, 1, 1) = 1.

Итак, поэтому g(A, 0, 1) = g(A, 0, 0) + g(A, 1, 1) = 1.

Сделайте то же самое с g(A, L2, H2), и вы получите это g(A, L, H) = g(A, L1, H1) + g(A, L2, H2) = 1 + 0 = 1.

@ У Наваза была хорошая идея визуализировать это в двоичное дерево, в основном вы начинаете с корня дерева:

{-1.5, 3.1, -5.2, 0.0}

На втором уровне итерации вы разбиваете массив на два:

     {-1.5, 3.1, -5.2, 0.0}
              /   \
             /     \
            /       \
           /         \
   {-1.5, 3.1}    {-5.2, 0.0}

На третьем слое вы снова делитесь:

     {-1.5, 3.1, -5.2, 0.0}
              /   \
             /     \
            /       \
           /         \
   {-1.5, 3.1}    {-5.2, 0.0}
      /   \          /   \
     /     \        /     \
 {-1.5}   {3.1}  {-5.2}   {0.0}

На данный момент L==H, поэтому мы можем оценить узлы:

     {-1.5, 3.1, -5.2, 0.0}
              /   \
             /     \
            /       \
           /         \
   {-1.5, 3.1}    {-5.2, 0.0}
      /   \          /   \
     /     \        /     \
 {-1.5}   {3.1}  {-5.2}   {0.0}
    |       |       |       |
    0       1       0       0

и чтобы найти возвращаемые значения, мы подытожим:

     {-1.5, 3.1, -5.2, 0.0}
              /   \
             /     \
            /       \
           /         \
   {-1.5, 3.1}    {-5.2, 0.0}
      0+1=1          0+0=0

и, наконец,

     {-1.5, 3.1, -5.2, 0.0}
             1+0=1

Answer 2

и M = 1, так как это его int-return g (A, 0,3) + g (A, 2 3)

Вот первая проблема.Если M = 1, то как вы говорите, что это return g(A,0,3) + g(A,2, 3)?

Это должно быть:

return g(A,0,1) + g(A,2, 3)
           //^ this should be 1

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

Мое предложение будет:

• Возьмите карандаш и белую бумагу.Будьте готовы нарисовать двоичное дерево, которое расширяется вниз
• Запишите корневой узел как g(A,0,3);.Это первый вызов.
• Затем создайте два дочерних узла: левый и правый
• Запишите g(A,0,1) в качестве левого узла и g(A,2,3) в качестве правого узла.
• Затем снова создайте два дочерних узла каждого дочернего узла и продолжайте рисовать узлы, повторяя этот шаг, пока условие if не станет истинным.
• Как только условие if станет истинным, прекратите создавать новые узлы (в этом случаеветвь) и поднимитесь к корневому узлу, суммируя значения узлов, которые встречаются на пути.
• То, что вы получите в корневом узле, - это возвращаемое значение исходного вызова из main().