专栏首页LINUX阅码场宋宝华:递归的出口在哪里? (除夕创作年度最后一篇文章)

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

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

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

本文分享自微信公众号 - Linux阅码场(LinuxDev)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • bug诞生记——无调用关系的代码导致死锁

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    方亮
  • 进程管理工具之top、htop、glances、dstat

    进程管理经常用到的工具有:top、htop、glances、dstat,下面一一介绍。

    二狗不要跑
  • vmware克隆linux虚拟机网卡无法上网的解决办法

    在学习Linux时候,经常需要克隆生成多台虚拟机以搭建内网环境。但是克隆生成的虚拟机网卡MAC错误,却无法正常联网。

    二狗不要跑
  • MySQL性能分析、及调优工具使用详解

    vmstat、sar(sysstat工具包)、mpstat、oprofile、nicstat、dstat、iotop、tsar、iostat 掌握几个即可,功能...

    二狗不要跑
  • CentOS下配置VNCServer,重启服务仍然生效

    分别切换到这几个账户下,执行vncpasswd命令,生成VNC访问用的密码,这里演示就设置为11111、222222、333333

    二狗不要跑
  • Samba网络文件共享服务介绍

    Samba是一个能让Linux系统应用Microsoft网络通讯协议的软件,而SMB是Server Message Block的缩写,即为服务器消息块,SMB主...

    二狗不要跑
  • Percona-tookit学习笔记(二)

    例如:pt-mysql-summary --user=root--password=root -h localhost|pt-align  【pt-mysql-...

    二狗不要跑
  • logwatch配置笔记

        https://segmentfault.com/a/1190000002537665

    二狗不要跑
  • 单机版MongoDB的zabbix监控

    最近公司新上了几个mongodb的项目(单机版MongoDB),需要坐下监控。之前有一个监控模板,但是效果不好。于是重新去google了一把,有了如下记录。

    二狗不要跑
  • Percona-tookit学习笔记(三)

        pt-query-digest可以从普通MySQL日志,慢查询日志以及二进制日志中分析查询,甚至可以从SHOW PROCESSLIST和MySQL协议的...

    二狗不要跑

扫码关注云+社区

领取腾讯云代金券