如何计算递归
发布网友
发布时间：2022-04-23 10:01
共1个回答
热心网友
时间：2023-10-10 15:16
举个简单的例子吧,1*2*3*4*5 ;
#include< iostream >
using namespace std;
int Fun( int val )
{
if( n > 1 )
return val * Fun( val - 1 ); // 最难理解的相信就是这一步吧
return val;
}
int main()
{
cout << Fun( 5 ) << endl ;
return 0;
}
首先,第一次调用Fun函数时,val == 5;
所以好好分析一下这段代码
if( val > 1 )
return val * Fun( val - 1 ) ;
第一次调用时 val == 5, 条件成立, 函数返回 val( 等于5那个 )乘以用实参 4 ( 也就是val - 1 的值 ) 调用的那个函数的返回值( 也就是自身 )...
看到这里先不要头晕, 这只是第一步,还有很多步调用,其实跟循环是差不多的.
函数调用有一个返回值, 如果返回值是一个表达式,就先求解表达式的值再返回,被函数返回时从调用函数处的下一个语句继续执行,如果没有理解C语言的这两句话,这就很难理解递归了.
下面是整个程序的流程
1, 用 val == 5 调用 Fun, 执行到 if 语句, 条件成立 执行 return val * Fun( val - 1 ), 由于函数调用操作符 () 优先级高于算术操作符, 因此表达式的求解顺序是先调用函数, 再 用 val * 返回值;
2, 用 val == 4 的值调用 Fun,后面的步骤和用 val == 5调用 Fun 的步骤是一样的;
3, 用 val == 3 的值调用 Fun;
4, 用 val == 2 的值调用 Fun;
5, 用 val == 1 的值调用 Fun, 这时的 if 语句条件不成立, 于是执行后面的
return val 的值( == 1 );
6, 那这个 val == 1 的值返回到哪里去了呢? 刚接触递归的人可能会很容易联想到是 main 函数调用 Fun 的, 那这个值也返回到 main 函数中去了. 其实不是,返回值为1的Fun函数是谁调用的?是 val == 2 时的Fun函数调用的,也就是第4步的if 语句后面的表达式是 return 2 * Fun( 2 - 1 ),理解这点就好办了,第六步就开始求解前面还没执行的算术操作( 由于函数调用操作符 () 优先级高于算术操作符, 因此表达式的求解顺序是先调用函数 ).也就是把第5步的返回值用于求解第4步时里的表达式;
7, 在上一步骤中,求解出 2 * Fun( val - 1 )的值, 又把它返回给它的调用者
,就是把值 3 返回至第3步;
8, 把第3步的得出的值返回第2步;
9, 把第2 步得出的值返回第1步;
10, 在第1步,记得这次调用是main函数调用的,因此返回到main函数中的cout << Fun( 5 ) << endl, 输出结果;
整个递归过程就完成了,可以看到递归也是一个循环,但它比一般的循环计算的步骤多了很多,所以它的效率普遍是比较低的,而且操作系统把每一次的调用装进一个栈中记录起来,它耗费的内存也是比较大的,在深层的递归调用或在递归函数中定义较大的数据容易造成栈溢出,但有时( 对初学者来说不见得 )用它来解决问题却能让代码清晰,容易编写.
