c++ - 如何跟踪递归函数 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 返回什么以及函数做了什么

这是我到目前为止得到的

第一次调用是 g(A , 0 ,3)-total 跳过 IF 语句和 M = 1 因为它是一个 int-返回 g(A,1,3) + g(A,2 3)

第二次通话 - g(A,1,3) 再次跳过 if 语句 - 米 = 0; - g(A,2 3) 再次跳过if语句 - M= 2;

第三次通话-g(A, 0,0,) 返回 0-g(A,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 .

@Nawaz 有一个将其可视化为二叉树的好主意，基本上您从树的根部开始:

{-1.5, 3.1, -5.2, 0.0}

在第二层迭代中，将数组分成两部分:

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

在第三层，你们再次 split :

     {-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