欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-27 19:06:38
01递归的出口迭代的是人,递归的是神。递归的出口,在于停止递归。当递归函数在某条件成立后不再调用自身,即意味着递归会终止。func(){ if(co......

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