递归的解释:
递归(英语:Recursion),又译为递回,
在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。(本文要讨论的重点)
递归一词还较常用于描述以自相似方法重复事物的过程。(指一种行为)
递归的使用描述
思考下面的blah()函数会发生什么?
它会无限调用自己。blah()会调用自己,被调用的blah()会再调用自己,无限循环下去。
blah()会无限调用自己。你觉得调用栈会变成什么样?
在无限递归中,计算机会一直把同一个函数压入调用栈。调用栈的大小不断增加,最终会耗尽计算机的短期存储。这就会导致栈溢出错误,即计算机会停止递归然后报错:“没内存了,不干了。”
图像辅助理解:
递归和循环的关系?
大部分的编程场景里,递归能做的事情,都能转换为循环结构去做。
同理,大部分使用循环的场合能替换为递归。
先来继续探索递归的工作方式。
当number为0时,代码不会再调用countdown(),而是直接返回。这样就不会无限调用下去。在递归术语中,这种函数不再继续递归的情形称为基准情形。因此0就是countdown()函数的基准情形。每个递归函数都需要至少一个基准情形才能避免无限调用。
function countdown(number) {
console.log(number);
if(number === 0) {
return;
} else {
countdown(number - 1);
}
}
而阅读递归代码,从基准情形开始慢慢向上分析是理解递归代码的好方法。
解释如下代码:
def factorial(number)
if number == 1
return 1
else
return number * factorial(number - 1)
end
end
解释这段代码在计算机内部都做了什么操作:
在计算机执行到factorial(3)的end关键字前,factorial(3)并未执行完。因此我们遇到了一种奇怪的情况。计算机还未执行完factorial(3),却要在执行factorial(3)的过程中开始执行factorial(2)。
在计算机执行到factorial(3)的end关键字前,factorial(3)并未执行完。因此我们遇到了一种奇怪的情况。计算机还未执行完factorial(3),却要在执行factorial(3)的过程中开始执行factorial(2)。
但这并未结束,因为factorial(2)还会调用factorial(1)。这听起来有些不可思议:在执行factorial(3)的过程中,计算机调用了factorial(2)。而在执行factorial(2)时,计算机又调用了factorial(1)。
从结果来看,在执行factorial(1)时,factorial(2)和factorial(3)都仍处在执行过程中。
计算机该如何记录这些过程呢?
它需要记得,在执行完factorial(1)之后返回并执行factorial(2)。然后在执行完factorial(2)之后返回并继续完成factorial(3)。
计算机使用栈来记录正在调用的函数。这个栈有一个恰如其分的名字——调用栈。
总结:
但能使用递归并不代表应该使用递归。递归并不比for循环优雅或者高效多少。使用递归还是循环,需要思考一下,
- 如果有具体的循环次数,适合用循环,
- 如果没有具体的循环次数,适合用递归。
递归的使用场景
学习了递归的原理之后,就可以用递归来解决一些原本无法解决的问题了。有一类问题很适合递归:这类问题有很多层,但我们不知道到底有几层。
-
需求:递归删除系统文件;(并不能知道这个文件夹下还有多深的文件夹)
-
需求: 需要将评论列表中所有子评论取出。这种情况下需要用到递归;
递归的思想
递归的思想是,它通常把一个大型的复杂的问题转化为一个与原问题相似的问题,以这样的思路去解决问题,这样可以极大的减少代码量,
递归的能力在于用有限的语句来定义对象的无限集合。
- Recursion Function 笔记recursion function笔记 recursion 函数function机制 笔记 recursion eventlet exceeded windows recursionerror comparison recursion exceeded extensions recursion detected loading optimization exploring recursion convex references recursion lecture4 lecture function verilog笔记task 算法recursion golang in