递归、迭代和尾递归

写这篇博客的原因是昨天做了一道编程题

Given a binary tree, return the postorder traversal of its nodes’ values.

Note: Recursive solution is trivial, could you do it iteratively?

简而言之题目要求用postorder并且是迭代的方式print出整个二叉树。

这道题还是很简单的,主要是要保存好节点的轨迹,很容易想到用先进后出数据结构的stack。这个不是这篇博客的重点,想知道具体代码实现的童鞋可以参考我的答案

受到SICP的影响,我看到这道题的第一个想法不是最后实现中的while循环迭代而是尾递归==当然了,我其实早就不记得尾递归具体的含义了。当时只是想着while和for循环不是和尾递归等价么。。。结果是我用尾递归的方法写完并且access后突然意识到我写的根本不是尾递归而是普通的递归,汗==#

进入正题,下面总结一下递归、迭代和尾递归这三个概念(概念来自维基百科)。

递归(recursion)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。

迭代(interation)是程序中对一组指令(或一定步骤)的重复。它既可以被用作通用的术语(与“重复”同义),也可以用来描述一种特定形式的具有可变状态的重复。

在计算机科学里,尾调用是指一个函数里的最后一个动作是一个函数调用的情形:即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归,是递归的一种特殊情形。

现在来讲讲它们三者的区别与联系。

首先递归是迭代的一种情况。为了方便,下面我们提到的迭代都不是递归类型的迭代,请勿混淆。递归适用的场景比较特别,通常是为了解决三类问题(引自漫谈递归和迭代):

  1. 数据的定义是按递归定义的。(Fibonacci函数)
  2. 问题解法按递归算法实现。(回溯)
  3. 数据的结构形式是按递归定义的。(树的遍历,图的搜索)

相比迭代,用递归解决这些问题来的更轻松,别人理解起你的代码也更加容易。但是递归有它自身的问题,每一次递归基本都需要在栈上申请一块新的空间,如果你干得漂亮的话用一个递归爆掉一个栈也不是很难的事情。除此之外,个人认为递归相对迭代来说和计算机本身的设计原理有些不搭,同样的功能递归应该要慢一些。 这里我们拿leetcode里的算法题来对比一下二叉树遍历按preorder遍历时的递归代码和递归代码:

尾递归是我当初在看Lisp时了解到的一个概念。尾递归是一种特殊的递归,它通过在尾部调用自己实现递归,这种方式会被一些函数式编程语言的编译器优化,不储存栈信息。这样的话尾递归就同时具备了递归方法的易懂易写和迭代的低空间消耗等优点。不过尾递归对于树型的递归(Tree Recursion)是不适用的。还有,一般函数式编程语言支持尾递归优化,Java和C++之类的似乎不怎么支持吧。 这里提供SICP中尾递归和普通递归的例子做比较:

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注