先来个场景: 下班了,你带着女友去电影院看电影~(没有女友?快私信我,组里各种白富美!加班没时间?快私信我,组里加班少!) 于是你开始展示你智慧的一面了,先问前排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。 但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问~ 直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。 这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”,所以叫“递归”。
举例理解递归:数组求和举个代码的例子理解下递归:对数组求和。 假设对 伪代码:
写真实的代码:
可视化递归过程上面看完之后,可能还是有点点蒙圈,感觉似懂非懂~ 没事,可视化代码运行,就明白了!可视化的过程,也是调试的技巧! 先可视化上面的数组求和:
执行代码:
再联系本文开头的话,“递”和“归”的过程,就能看出来了~ 大问题转化为更小的同一问题,一直转化到最小级别的问题,先解决最小级别的问题,然后大一点的问题就解决了,一直到原先的问题就会被解决~ 可视化代码的步骤:
怎么写递归两步:
再举个例子: 有一组数:1,1,2,3,5,8,13,21........ 问第 n 个数是什么? 细细看看,其实就是斐波拉契数列,后面一个数等于前两数之和。
其实就是前两个数:
第 n 个数就是前两数之和:
撸码:
可以试试可视化过程,这里我就不演示了,当作业了~ 递归的缺陷和解决方案两个大缺陷:
可以看到,递归的过程就是函数调用的过程,反复调用函数,函数调用栈会很高,一定数量级之后,会溢栈,专业名词就是 这种缺陷的一个解决办法是:提前规定最大深度,超过深度之后直接报错。
重复计算度高怎么理解呢? 比如计算第 5 个数,等价于 这种缺陷的一个解决办法是:用哈希表保存已经求解过的 f(k),调用到 f(k) 时,哈希表有则直接返回,不需要重复计算了。当然代价是,空间复杂度变高。
除了堆栈溢出、重复计算度这两个大问题,时间上,过多的函数调用会积聚成一个可观的时间成本;空间上,调用一次就会在内存栈中保存一次现场数据,同样也会有可观的空间成本。 怎么将递归代码改写为非递归代码递归的好处是代码简洁易理解,坏处就是上面的。能不能将其转化为非递归代码呢?答案是肯定的!递归的过程可以理解为函数调用栈的过程,我们可以手动模拟进栈出栈,也就是迭代循环!
“手动”递归,并不是说没有缺点,虽然没有那么多函数调用,但是重复计算度依然很高。另外,迭代循环,对于线性结构的还好理解些,对于非线性结构的理解起来会更困难。 引用
来源:颜酱 https:///post/6948718907918123044
|
|
来自: 新用户49272060 > 《待分类》