如何跟踪递归函数C ++ [英] how to trace a recursive function C++

问题描述

  #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）; 
 
系统（暂停）; 
 return 0; 
} 
  

它询问函数g返回的是什么， / p>

这里是我到目前为止

第一次调用是g（A，0，3）
-total跳过IF语句并且M = 1，因为它是一个int
-return g（A，1,3）+ g（A，2 3）

第二次调用
- g（A，1,3）再次跳过if语句
- M = 0;
- g（A，2 3）再次跳过if语句
- M = 2;

第三次调用
-g A，0,0，）
return 0
-g（A，3,3）
return 0;

只是返回0？

我猜猜它正在分割中间值和某种二分搜索？

解决方案

计算数组中有多少个数字大于0是一个复杂的方法。如果你试图运行这个编译器，返回值为1，因为数组中大于0的唯一数字为3.1。

第一次运行时：

  { -  1.5，3.1，-5.2，0.0} 
 0 1 2 3 
 LH 
  

那么由于 L = 0 和 H = 3 g（A，L，M）时，c $ c>， M =（0 + 3）/ 2 = 3/2 = 1 ）+ g（A，M + 1，H），你分成两部分：

  -1.5，3.1，-5.2，0.0} 
 0 1 2 3 
 LH 
 L1 H1 L2 H2 
  

让我们来做左边 g（A，L1，H1）= g（A，0，1） >

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

，因为 L1 = 0 ， H1 = 1 ，因此 M1 =（0 + 1）/ 2 = 1/2 = 0 ，并再次分支到 g（A，0，0）和 g ）：

  { -  1.5，3.1，-5.2，0.0} 
 0 1 2 3 
 LH 
 L1 H1 L2 H2 
 L11，H11 L12，H12 
  

$ b因为 -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）= c c 使用 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} 
  

$ b b

在第二层迭代中，将数组拆分为两个：

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

并找到返回值，我们总结： p>



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




#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;
}

its asking me what is return by the function g and what the function does

here is what i got so far

first call is g(A , 0 ,3) -total skip the IF statement and M = 1 since it its a int -return g(A,1,3) + g(A,2 3)

second call - g(A,1,3) skipp the if statement again - M = 0; - g(A,2 3) skip the if statement again - M= 2;

third call -g(A, 0,0,) return 0 -g(A,3,3) return 0;

so it just return 0?

and i am guessing it is dividing the middle value and some sort of binary search?

解决方案

It's a convoluted way to count how many numbers in the array is greater than 0. And if you try to run this in a compiler, the return value is 1 because the only number that is greater than 0 in the array is 3.1.

at first run:

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

then since L=0 and H=3, M = (0+3)/2 = 3/2 = 1 when you get to g(A, L, M) + g(A, M+1, H), you branch into two:

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

let's do the left part g(A, L1, H1) = g(A, 0, 1) first:

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

again since L1=0, H1=1, and so M1 = (0+1)/2 = 1/2 = 0 and you branch into two again g(A, 0, 0) and 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

on the left part, since -1.5 <= 0 therefore g(A, L11, H11) = g(A, 0, 0) = 0, on the right part, since 3.1 > 0 therefore g(A, L12, H12) = g(A, 1, 1) = 1.

So therefore g(A, 0, 1) = g(A, 0, 0) + g(A, 1, 1) = 1.

Do the same with g(A, L2, H2), and you get that g(A, L, H) = g(A, L1, H1) + g(A, L2, H2) = 1 + 0 = 1.

@Nawaz had a good idea of visualizing this into a binary tree, basically you start with at the root of the tree:

{-1.5, 3.1, -5.2, 0.0}

At the second layer of iteration, you split the array into two:

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

At the third layer, you split again:

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

At this point L==H so, we can evaluate the nodes:

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

and to find the return values, we sum up:

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

and lastly

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

这篇关于如何跟踪递归函数C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！