TOP

C++ 递归
2019-11-18 11:39:25 】 浏览:25
Tags:C++ 递归 阶乘 算法

递归是什么?wiki上这么写:

  1. 递归(英語:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

说得很抽象,我们在看看另一说法:

  1. 递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。

  2. 在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。

有几个明显的特点:

  1. 可以将问题由大化小

  2. 解决问题是同一个方法,而且就是是自身

  3. 有明显的结束条件

先看看下面的例子:

  1. 计算10的阶乘10!在数学中,正整数的阶乘是所有小于及等于该数的正整数的积,计为n!

  2. 10!=10*9*8*7*6*5*4*3*2*1

阶乘是很常见的数据计算方法,按公式可以分解下计算:

  1. 10!=10*9*8*7*6*5*4*3*2*1

  2. =10*(9*8*7*6*5*4*3*2*1)------10*9

  3. =10*(9*(8*7*6*5*4*3*2*1))-----10*9*8

  4. =10*(9*(8*(7*6*5*4*3*2*1)))-----10*9*8*7

  5. =10*(9*(8*(7*(6*5*4*3*2*1))))-----10*9*8*7*6

  6. =10*(9*(8*(7*(6*(5*4*3*2*1)))))-----10*9*8*7*6*5

  7. =10*(9*(8*(7*(6*(5*(4*3*2*1))))))-----10*9*8*7*6*5*4

  8. =10*(9*(8*(7*(6*(5*(4*(3*2*1)))))))-----10*9*8*7*6*5*4*3

  9. =10*(9*(8*(7*(6*(5*(4*(3*(2*1))))))))-----10*9*8*7*6*5*4*3*2

  10. =10*(9*(8*(7*(6*(5*(4*(3*(2*(1)))))))))-----10*9*8*7*6*5*4*3*2*1!

可以看出每个等式都可以分解为两部分相乘,而且上一个数的阶乘都可以转化为下一个数的阶乘乘以本数。

下面看看我们的实现:

  1. #include"stdio.h"

  2. intRecursion(int t)

  3. {

  4. if(t>1)

  5. {

  6. return t*Recursion(t-1);//分解为下一个数的阶乘

  7. }

  8. elseif(t=1){

  9. return1;//结束条件,递归到此为止,函数不再压栈

  10. }

  11. }

  12. int main()

  13. {

  14. int r =Recursion(10);

  15.     printf("%d\n",r);

  16. return0;

  17. }

编译执行:

  1. # g++ jiecheng.cpp 

  2. # ./a.out 

  3. 3628800

这个是基本的递归概念,在很多算法都会涉及,特别是查找、排序算法等。如果要深入了解递归的实现原理,需要对编译原理有一定的理解,函数栈的处理等,这里不在展开。



C++ 递归 https://www.cppentry.com/bencandy.php?fid=49&id=269392

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇套接字 下一篇GALAXY OJ NOIP2019联合测试2-普..