是什么是递归?-[all]-[编程理论]
递归是所有编程语言中,都会讨论到的一个问题。
Content Of Table
递归的通俗认识
编程领域的抽象
一个最简单的示例
一点总结
栈溢出问题
本示例的一点拓展说明
### 递归的通俗认识
编程是现实的抽象,这是能被应用到所有的编程概念的。
递归也是如此,其实递归,就是重复,循环, 我们大概上幼儿园的时候,其实就有过递归的概念。
![](https://img2018.cnblogs.com/blog/1735896/201912/1735896-20191220180001252-1957541256.png)
在一个故事中,不断的提到上一次讲过的故事
### 编程领域的抽象
我们知道,一个函数是可以调用另一个函数的,作为特例,如果函数调用了自己。那么就像故事中提到同样的故事一样。
我们把函数在运行的时候调用自己的情况,叫做递归。其实这样讲并不严谨,因为以上讲到的,实际只有递进,没有回归。回归是计算中的概念,我们可以大致理解为返回并销毁,以下说明。
### 一个最简单的示例
我们定义一个自调用的最简单的情况,定义一个cal函数,如下:
```javascript
//js
function cal(a){
return a + cal(a-1)
}
console.log(cal(3))
其执行过程如下:
<center>![](https://img2018.cnblogs.com/blog/1735896/201912/1735896-20191220225318405-1003795447.png)</center>
显然,这不是我们希望的结果,由于程序无条件的执行,所以该程序理论上将无止尽的递进下去。但是在计算机中,是不被允许的,文章末尾<ud>[栈溢出问题](#栈溢出问题)</ud>
现在,我们为了不让这个程序无止尽递进执行,我们需要给它加上一些条件,例如:
```javascript
//js
function cal(a){
if(a>0){
return a + cal(a-1)
}else{
return 0
}
}
console.log(cal(3))
我们给程序加了一些判断,我们判断了a这个参数,如果它大于0,我们就准许它递归。如果它等于0了,我们就直接通过return终止程序,并且返回0。实现回归
以上程序执行结果为6,正确。 它的实现功能是:3+2+1+0
### 一点总结
- 递归,简单的来说,就是一个方法自己调用自己的这么一个过程
- 递归递归,递:指的是“递进”,归:指的是“回归,返回”。 所以,一般递归方法中会有判断,能让方法有条件的执行,有递,就要有归 否则,只递不归就会造成栈溢出,导致程序崩溃。因此,我们需要有条件语句在合适的时候终止递归。
### 栈溢出问题
在程序中,调用函数,是需要有“代价”的,那就是,要占用一片叫做栈(Stack)的内存空间。
当调用函数时,数据需要存储到栈里,当函数运行结束的时候,这些数据会从栈里被取出。
所以,可想而知,如果调用了很多函数,但是这些函数都不返回,不被处理掉,栈就会被塞满,数据就没有地方放了。
这种情况,叫做栈溢出错误。
对于程序运行而言,这是致命的错误,因此程序会被操作系统强行终止。
例如,如果以上示例,没有设置条件判断,就会产生以下错误(js):
![](https://img2018.cnblogs.com/blog/1735896/201912/1735896-20191220232122561-673785687.png)
本示例的一点拓展说明
虽然本示例用到的是一个最简单的递归方法。
但是仅通过此方法,就可以实现各种等差数列的求和:
![](https://img2018.cnblogs.com/blog/1735896/201912/1735896-20191221003044280-1263729883.png)
如果是a+x呢?、 * ?、 / ? 、更复杂的数学公式?
仅通过这个一个示例我们就可以轻松的实现:
- 形如:1+3+5+7+···+(2n-1) 这种奇数项求和
- 形如:2+4+6+8+···+2n 这种偶数项求和
- 形如:1+2+3+4+5+6+···+n 这种累加
- 甚至形如: 11+8+5+2+0 这种奇偶求和
最新文章
- Unicode、UTF-8、UTF-16和UTF-32的区别
- fontAwesome代替网页icon小图标
- eclipse中编译时enum出现cannot be resolved to a type错误
- ant有什么用
- C# 内存法图像处理
- nRF51822 SDK初体验
- [LeetCode]题解(python):025-Reverse Nodes in k-Group
- 文本变语音引擎 ekho
- dirname(_file_) DIRECTORY_SEPARATOR
- nyoj 数的长度
- 关于项目里server清楚缓存的代码
- Kaggle比赛:从何着手?
- Bugku-CTF之你必须让他停下+头等舱
- JS控制CSS3,添加浏览器兼容前缀
- Java开发笔记(九十一)IO流处理简单的数据压缩
- js的调用方式
- 软链接ln -s以及如何解决其产生“Too many levels of symbolic links ”的错误?
- poj_1042 贪心算法
- 树莓派安装、卸载docker
- Python的15个坑