追溯递归调用

Question

我对递归很陌生，我试图理解它是如何工作的，并试图跟踪它是如何接近于下面编写的代码找到answers.This的，查找整数数组中搜索的数字的最后一个索引，例如，in[4]={1,2,3,2}和这个数组中搜索的数字是2。这个问题的答案是3，因为它是最后一个index.Now，我将尝试编写这段代码是如何实现的，it.The in[]是输入数组，stin是起始整数，要找到的数字是num。

1. 在line和lastINdex(in，stin+1，size，num)中，函数被递归地调用到它的基本情况，即当它的大小变成stin==siz.then时，它的值被返回给调用它的函数，.my问题是这个函数如何在递归语句之后到达该行。请提供此代码的说明。 int lindex(int in[], int stin, int num){ int size=strlen(in); if(stin == size){ return -1; } int ans = lastIndex(in, stin + 1, num); if(ans != -1){ return ans; }else{ if(in[stin] == num){ return stin; }else{ return -1; } } }

Answer 1

实现将通过递归调用返回到行。如果一个人不熟悉递归，它可能会有一些时间来适应它。如果您能够使用调试器，我强烈建议使用它并检查调用堆栈和局部变量值。但是，递归调用的顺序可以按下面的方式展开，使用示例使用伪代码表示法，其中插入值。

1. call lindex({1,2,3,4}, 0, 2):
   int size=strlen(in); // assigns 4
   if(0 == 4){          // condition is false
   }
   int ans = lastIndex({1,2,3,4}, 1, 2); // assigns 3, as we see below
   if(3 != -1){         // condition is true
       return 3;
   }

2. call lindex({1,2,3,4}, 1, 2):
   int size=strlen(in); // assigns 4
   if(1 == 4){          // condition is false
   }
   int ans = lastIndex({1,2,3,4}, 2, 2); // assigns 3, as we see below
   if(3 != -1){         // condition is true
       return 3;
   }

3. call lindex({1,2,3,4}, 2, 2):
   int size=strlen(in); // assigns 4
   if(2 == 4){          // condition is false
   }
   int ans = lastIndex({1,2,3,4}, 3, 2); // assigns 3, as we see below
   if(3 != -1){         // condition is true
       return 3;
   }

4. call lindex({1,2,3,4}, 3, 2):
   int size=strlen(in); // assigns 4
   if(3 == 4){          // condition is false
   }
   int ans = lastIndex({1,2,3,4}, 4, 2); // assigns -1, as we see below
   if(-1 != -1){         // condition is false
   }else{
       if(in[3] == 2){   // condition is true
       return 3;
   }

5. call lindex({1,2,3,4}, 4, 2):
   int size=strlen(in); // assigns 4
   if(4 == 4){          // condition is true
       return -1;
   }

如果我们讨论各个步骤的语义，则实现变得更容易访问。首先，检查开始索引是否指向数组，在这种情况下，无法找到所需的数字并返回-1。否则，我们将在数组的尾部寻找要查找的数字。如果可以在那里找到它，则返回在递归调用中找到的索引。否则，我们将测试当前位置是否相等，以查找所需的数目，因为它不会发生在数组的尾部。总之，这将返回搜索数字最右边出现的索引(如果包含它的话)。

从递归调用返回的“逐步后退”是通过调用堆栈完成的；每个递归调用都有自己的一组局部变量。