本文参照此处实现: 递归函数转非递归(通用方法)[1/2]——数据结构 递归函数转非递归(通用方法)[2/2]

先说总结,这种方案总的来说就是机械化的强转,时间复杂度和空间复杂度没什么变化,唯二的优点可能是1. 不会爆栈,2. 节省了函数调用的开销

而且最终产出的代码效果不那么美观,比较冗长

思路是:当发生递归调用时,模拟函数调用的压栈。并处理入参返回值记录返回到当前栈的时候该继续从哪里执行

阅读全文

原文: Tricks of the trade: Recursion to Iteration, Part 4: The Trampoline

这是关于将递归算法转换为迭代算法系列文章中的第四篇。如果你没有阅读过前面的文章,你可能想在继续之前阅读。

在我们系列的第一篇文章中,我们展示了如果你能将一个算法的递归调用转换为尾部调用,你就可以消除这些尾部调用,使用简单方法创建一个算法的迭代版本。在这篇文章中,我们将看看另外一种消除尾部调用的方法:trampoline

trampoline背后的思想是:在进行尾部调用之前,手动将当前执行的帧从栈中移除,消除栈堆积

阅读全文

原文: Tricks of the trade: Recursion to Iteration, Part 3: Recursive Data Structures

这是将递归算法转换为迭代算法系列的第三篇。如果下面的任何内容看起来令人困惑,你可能想先阅读前面两章的内容

这是我没有计划的一篇附加文章。之所以写它,是因为在上一篇文章的评论中,有读者要求我展示一个不那么数学化的例子,并建议使用树遍历。所以这就是这篇文章的主题。我们把一颗二叉树扁平化成一个列表,先是递归,然后是迭代

阅读全文

原文: Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick

这是将递归转化成迭代系列的第二篇。如果你还没有读过上一篇,你应该读一下。它介绍了一些有帮助的术语和背景知识。

上次,如果你还记得的话。我们讨论了将递归函数转化为迭代函数的简单方法。顾名思义,这种方法很简单,而且很机械。唯一潜在的问题是,要使用这种方法,你必须将函数中所有的递归调用转化为尾递归。

这个任务可能很棘手。因此,我们还讨论了将递归调用转化为尾递归的秘密函数技巧。这个技巧适用于简单的递归调用,但当调用不那么简单的时候,就需要一个更强大的版本。

这就是这篇文章的主题:时空旅行的秘密。这就像将T-800送到过去(来自电影终结者),终止一个函数的递归性

是的

但是我们得慢慢来。所以,坚持使用早起的例子,为后面困难例子做好准备。

说够了!让我们从一个实际的例子开始。

如果你想要另外一个例子,这里还有一个斐波那契数列的逐步转化

阅读全文

原文链接: https://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html

另一个标题:我希望python有尾递归消除

递归编程很强大,因为它很容易映射到通过归纳法来证明,这使得设计算法和证明算法的正确性变得容易。

但是很多流行的编程语言对递归的支持很差。在python中将一个大的输入丢进递归算法中,你可能会碰到运行时的递归限制。提高限制,你可能会耗尽栈空间从而触发段错误。

这些都很操蛋。

因此,一个重要的技巧就是知道如何将递归算法转换成迭代算法。这样以来,你就可以设计、证明和编写初步递归代码。在完成之后,你可以通过一系列机械化的步骤把你的算法转换成等价的迭代形式。

把递归变成迭代,这个话题足够吸引人,所以我打算做成一个系列的文章。尾部调用,trampolines(蹦床, 就是两个函数互相调用,可以参照[译] 使用JavaScript中的蹦床函数实现安全递归),continuation-passing style(参照CPS) 等等

本篇文章中,我们只看一个简单的方法和一个辅助的技巧。

阅读全文

利用python去除PDF水印

发布在 python

最近手上有一份PDF资料,水印太多。非常影响阅读。所以写了一个脚本去掉水印。在两年前我折腾过给PDF增加隐藏的文本,说实话,个人感觉PDF格式还是很复杂的。好在很多PDF常见需求都有无数前人躺过坑。在网上搜了一下找了一个比较靠谱的改了一下

阅读全文

国内观看Netflix

发布在 python

元旦三天假,比较无聊,看了两天的Netflix,起因是网上很多教程说这家视频网站对代理封杀很严重,即使付费还不一定能看,搞的好像很吸引人的样子,这勾起了我的好奇心,想看看这个视频网站是啥样的,去淘宝花十块钱买了一个月的共享账号,折腾了一下还是能看了!给我的感觉就是视频清晰不卡顿(即使代理一点也不卡),至于视频数量,不敢恭维,可能网上找盗版资源下载更好一点,突破代理限制的方法就是服务器使用ipv6地址去连接Netflix

阅读全文

ocr.ficapy.com 后台实现

发布在 python

因为个人需求,写了一个很小众的作品,https://ocr.ficapy.com,我给它起的项目名是pdfaddtext,用途是给扫描版本的PDF文件加上搜索功能。使用场景是我有几本扫描版本的PDF书籍(网上有特别多的扫描版书籍),有时候想搜索书中有没有提到某个知识点,纯图片是无法搜索的,你只能凭记忆去找。本项目作用就是将PDF的文本内容识别出来,然后写入一层隐藏的文字层,这样PDF阅读器就能够搜索这些文字了,同时尽量保证将识别出来的文字写到原图片对应的位置,类似的工具有OCRmyPDF,它的缺点很明显,使用Tesseract OCR引擎,对比识别效果,简直被商用OCR吊打。

最开始有了这个想法,我大概花费了一个下午的时间用python写出了基本的demo。将每一页PDF转换成图片,然后用免费的OCR服务去识别,得到结果,最后合并出一个新的pdf出来。过程算是比较顺利。本着独乐乐不如众乐乐的心态。我计划将它转变成一项web服务,于是挖坑之旅就此开始了

TLDR

阅读全文

Python高级多线程并发

发布在 python

在多线程多进程当道的年代这个被称为高级并发的模块还是很令人惊艳的。concurrent.future模块的厉害之处在于封装了多线程、多进程、锁、队列到一起。这些细节使用者都不需要知道。四五行代码能实现以往二三十行实现的效果。而且多线程和多进程的使用方式完全一样,堪称完美杰作。可惜,现在已经是异步时代了,主要是因为tornado用到了它的Future模块。我就看看它大概是怎样实现的

阅读全文

Python中的多线程锁

发布在 python

多线程是个坑爹的课题,有多线程就有锁。Python中有低级线程模块_thread、再封装一下就是threading、再来一下就是from concurrent.futures import ThreadPoolExecutor。其中涉及到的锁大概有Lock、RLock、Condition、Semaphore、BoundedSeamphore、Event。这么多看起来怪吓人的,其实这么多的锁全部只是由Lock演化出来的

阅读全文

ficapy

author.bio


author.job


深圳