|
今天来写写对递归的理解。 关于递归，百度搜索给出了很多答案。无非就是递归是一种思想，其代码量少，但执行效率不高等等。 递归其实分为"递"和"归"。递就是传递，就是将一个大问题细化成更小的问题，直到不能再小，那么这时候函数就得到一个最终的值，而这个值是我们可以知道的。这时候就执行"归"，函数带着那个最终的值逐级返回，返回直到第一次调用函数自身时，就终止了"归"，最终的结果返回给调用函数。 其实递归的难点有二: 1:递归就是函数直接或间接调用自身，那么它是怎么执行的呢？ 2:递归什么时候该终止呢？它又是怎么返回的？ 只要明白了这两点，理解递归就比较容易了。首先，我们要清楚函数调用的过程与返回。 用个简单的例子来说明一下: int s(int x); main() { int a=1; s(a); return 0; } int s(int x) { int y=2; return x+y; } 在这个程序里，main是主函数，s是自定义函数。在main里，调用了s函数。我们称main是调用函数，s是被调用函数。程序执行到s(a)，调用了s函数，给这个函数传了个参数a。 (注:这里的参数a是实参，s里的x是形参。) s函数被定义为了int型，它的返回值同样也是int型的。这点一定要记住。程序执行到s(a)，给s传了个参数，然后会留下一个返回main函数的入口地址，就转到s函数里去执行了。(main函数此时则是等待s函数执行完毕)。那么就会执行x+y，得到结果3，然后带着结果3，根据之前留下的返回main函数的入口地址返回到main函数中，程序控制权转交给main，main则继续往下执行后续语句。 当函数调用发生时，程序会像画面定格一样，保存当前场景。然后当被调用函数执行完毕后，会带着返回值返回到调用函数中。这就是函数调用大概的过程。 明白了函数调用的过程，下面就以那个阶乘的递归程序来详细了解一下递归的工作过程。 #include long fact(int ); int main() { printf("结果是:%ld",fact(4)); return 0; } long fact(int n) { long f; if (n>1) f=fact(n-1)*n; else f=1; return f; } 在main里传了个4给fact函数，然后使用fact的返回值输出。 程序转到fact函数里执行。判断4大于1，执行f=fact(n-1)*n。关键之处来了，这句又调用了fact这个函数，我们之前说过，调用一个函数，程序会保存当前场景，留下一个返回调用函数的入口地址，然后转到被调用函数继续执行。所以这里，程序会保存当前状态，留下一个返回到这里的入口地址，然后使用参数n-1，也就是3，转到被调用函数fact继续执行！而不是执行*n！然后程序继续判断3大于1，继续调用fact…以此类推。最后一直到n的值为1时，因为1不大于1，所以会执行else语句，直接给f赋为1。然后程序执行return f，f的值也就是1，返回。然后程序控制权转交到最后一次的调用函数，又会执行一次那个语句。也就是会返回到n-1=1时的那次。然后执行*n，此时n是2，1*2得2。然后带着这个结果继续返回调用函数。然后，继续逐级返回。每次返回，都是带着被调用函数的返回值。 最后，递归结束，控制权返回到最初的fact，得到结果24。函数返回到main，继续执行，输出fact最终的返回值24。 |
|
|
