宋宝华:递归的出口在哪里? (除夕创作年度最后一篇文章)
01
递归的出口
迭代的是人,递归的是神。递归的出口,在于停止递归。当递归函数在某条件成立后不再调用自身,即意味着递归会终止。
func()
{
if(condition)
//不再调func
func()
}
我们要理解,《恐怖游轮》的故事,对于现实的递归来讲,绝对是个bug。因为《恐怖游轮》没有出口,它只能是死循环。
西西弗斯(希腊语:Σίσυφος;又译西绪弗斯、薛西弗斯、西西佛斯等),是希腊神话中一位被惩罚的人。他受罚的方式是:必须将一块巨石推上山顶,而每次到达山顶后巨石又滚回山下,如此永无止境地重复下去。在西方语境中,形容词“西西弗斯式的”(英语:sisyphean)形容“永无尽头而又徒劳无功的任务” (来源*)。
这也不是正常的递归,没有出口!那么,它如何才能出去呢?必须创造一个条件,比如石头自己炸裂了,山垮了。
滚石头()
{
if(山垮了)
不滚了;
滚石头()
}
02
斐波那契问题
我们看看著名的斐波那契问题:假设一对刚出生的小兔,2个月后具备繁殖能力,可以生出一对小兔,而且此后的每个月都可以生出一对小兔,问一年后一共有多少对小兔?
这是著名的斐波那契数列
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
…
它满足F(n)=F(n-1) + F(n-2)
上述递归的出口,实际就是n=0和n=1的时候,都不再继续了。如果我们给上述函数传入参数5,其调用过程如下:
由此大家可以看出,递归有时候会把大量算过的值重新算一次。所以如果把已经算过的fib(3),fib(2)保存下来,后面不再算一次,则可以减少很多次的计算。另外,大家也可以看出,上述调用树的叶子节点,实际就是递归不再调用自己的节点。
03
目录遍历
遍历目录问题,写一个shell脚本遍历某目录以及子目录下的所有文件。
上述递归的出口,在于如果发现目录下的$i不是目录,就不再调用travese_dir函数。
04
库依赖
库依赖问题:写一个python脚本,根据ELF,分析它依赖的库,以及库依赖的库,画依赖图。
原理非常简单,任何一个elf文件,ldd命令可以show出来它对别人的依赖:
Bash依赖/lib/i386-linux-gnu/libtinfo.so.5,而/lib/i386-linux-gnu/libtinfo.so.5依赖/lib/i386-linux-gnu/libc.so.6,再继续,发现/lib/i386-linux-gnu/libc.so.6不再依赖谁,所以它成为递归的出口。
$ ./libdep-pic.py /usr/lib/firefox/firefox
得到如下图:
05
小偷偷最多钱问题
最后,来一个狠毒的。假设一个小偷,带着一个size为100的袋子去装东西,商店里面一共有n个东西,每个东西的size和价值是
(S1, v1), (S2, V2), ………………… (Sn, Vn)
如何在总size不超过100的情况下,这个袋子最多可以装价值多少的东西?这个小偷要怎么装?
最后祝大家除夕愉快!新春大吉!猪年大发!
如果您觉得有用,欢迎扫码打赏支持原创 |
本文地址:https://blog.csdn.net/juS3Ve/article/details/86764707