(Re)Write recursions easily

近来刷题,觉得递归实在神奇。对于有的题目,用循环实现思路很清晰,改成递归却变得非常抽象;另一些相反,递归的做法既简洁又容易理解,但换成迭代就怎样都不明白了。经过几次痛苦的思考之后,我发现其中还是有迹可循的,按照套路来做,至少思路不会走得太偏。 在维基上面发现的关于递归的笑话: To understand recursion, you must understand recursion. Write Recursion 审题分析过后,如果选择用递归,需要先明确两个最重要的组成部分: 边界条件,保证函数能够返回,不会无限递归下去 递进关系,也就是上下层递归调用结果的等式规律 比如求 factorial: def factorial(n): if n <= 2: return n return factorial(n - 1) * n 如果必要的话,还得考虑的是如何维护上下文的状态信息,目的是计算最终的返回值,有两种办法: 使用全局(outer scope)变量 利用参数进行传递 下面的写法就是利用了参数来保存中间的计算结果: def factorial(n, res): if n <= 2: return res * n return factorial(n - 1, res * n) 也就是所谓的尾递归,对于可以优化尾递归的语言确实可以看成这种方式是从上至下的,而常规的递归则是从下到上。但我理解递归都是先下去再上来的,尾递归只是选择了一去不返而已。 上面的例子比较简单,反转链表的代码就比较难理解一点: def reverse_list(head): if not head or not head.next: return head new_head = reverse_list_by_recursion(head.next) head.next.next = head head....

10-25 · 2 min