宋宝华：递归的出口在哪里？ (除夕创作年度最后一篇文章)

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的情况下，这个袋子最多可以装价值多少的东西？这个小偷要怎么装？

最后祝大家除夕愉快！新春大吉！猪年大发！