递归算法，简单却不简单的一种算法。
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。 ——百度百科-递归算法
递归算法是使用递归在程序设计语言中广泛使用的一种算法，递归是什么？递归是程序调用自身的编程技巧（百度百科）。递归在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法（维基百科）。
说白了，递归是一种方法，是对自身的调用。打个比方，我想吃苹果了，然后我做了一个计划。这苹果在一个程序里面就是数据，然后我制定的吃苹果的这一套计划，就是方法。我按照我制定的计划吃苹果就是用方法处理数据。我是怎么吃苹果的，我拿起桌子上这个苹果（这苹果是砸到牛顿的苹果），然后咬了一口（现在成乔布斯的了），然后在放回桌子上，我吃了苹果了，这计划就结束了。有说，你这苹果没吃完呢，没吃完就对了，我计划就是吃苹果，没说要吃完苹果，我要吃完苹果也简单，再拿起来，咬一口，放下，然后拿起来，咬一口，放下......直到我最后剩一口苹果核，我不能吃了，我这就结束了。
啃过一口的苹果
我把苹果从一个完整的苹果一步一步吃到苹果核，这个过程就是递归。递归有四个法则：
第一个是基准情形，是不用递归就能求解。我吃苹果，这次我不用递归了，我不拿起来放下，太费事，我一次拿起来，咔嚓咔嚓一口一口吃完，这是迭代，最终结果一样，我剩下了苹果核。用递归方式，我吃苹果这过程，最后剩一口苹果核，我不能再吃了，这就是基准情形，也就是递归出口，从这里我结束了我吃苹果这过程，我结束了递归。
第二个法则是不断推进，也就是我的递归必须能朝着我的基准情形的方向推进。我每吃一口苹果，我就离苹果核，也就是基准情形更进一步。
第三个法则是设计法则，是假设所有的递归调用都能运行。比如我吃的这个苹果，一口下去，嗬，半条虫子，我这没法吃了，这就没法结束了，从某种意义上讲，我这没做容错处理，这递归就不算递归了，因为没法继续。
第四个法则是合成效益法则，是在求解一个问题的同一个实例时候，切勿在不同的递归调用中做重复性工作。什么意思呢，就是我吃苹果不喜欢吃皮，然后我在开始的时候（吃苹果当然不能再所有时候都吃到苹果皮，只是有皮的地方能吃到）吃一口苹果，把皮吐出来，吃一口吐一口，我这就重复了，影响效益了。所以我直接在开始把皮削好就成了。
我在文章的开头说过这么一句话：递归算法，简单却不简单的一种算法。为什么我说递归算法简单却不简单？
从算法本身讲，算法的级别、难度、理解度都是极其简单的，深一步能有分治策略，这是个底层的算法，可以说得上是一种元算法了，况且就理解起来而言，递归算法算得上是最简单的一种算法了。可我又说递归算法是不简单的一种算法，递归算法本身的步骤是有限的，算法的深度是有限的，但是算法能执行的深度是无限的。我的老师给我讲过一个故事：UNIX系统的第一个版本的系统，本身是用了六个程序块相互递归调用，然后组成了这个完美、优雅的UNIX系统（仅从授课教师听到，未曾在网络找到文字记载）。
计算机科学大师尼克劳斯·维尔特描述递归的一句话：递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。
网友评论