递归的定义

在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。

若调用自身，称之为直接递归。

若过程或函数A调用过程或函数B，而B又调用A，称之为间接递归。

在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以主要讨论直接递归。

如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，称为尾递归。

以下是求n!（n为正整数）的递归函数。它属于什么类型的递归。

解：直接递归函数。又由于递归调用是最后一条语句，所以它又属于尾递归。

递归算法通常通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解。

递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了算法的代码量。

一般来说，能够用递归解决的问题应该满足以下3个条件：

需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。

递归调用的次数必须是有限的。

必须有结束递归的条件来终止递归。

何时使用递归

有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci（斐波那契）数列等。

数据结构是递归的

有些数据结构是递归的。如单链表就是一种递归数据结构。

求一个不带头结点单链表p中所有data成员（假设为int型）之和。

问题的求解方法是递归的

设Hanoi(n，x，y，z)表示将n个盘片从x塔座借助y塔座移动到z塔座上

一般地，一个递归模型是由递归出口和递归体两部分组成。

递归出口确定递归到何时结束，即指出明确的递归结束条件。

递归体确定递归求解时的递推关系。

递归出口的一般格式如下：

递归体的一般格式如下：

递归与数学归纳法

采用数学归纳法证明1+2+…+n=n(n+1)/2

递归的执行过程

遇到递归出口发生“质变”，原递归问题便转化成可以直接求解的问题。

求值过程：

例如：求5!。

系统内部如何执行递归算法

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。

为了保证递归函数的正确执行，系统需设立一个工作栈。

（1）执行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址。

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址进栈。

（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。

例如，有以下程序段：

程序执行时使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)表示，那么自栈底到栈顶保存的信息的顺序是怎么样呢？

用递归算法的形参值表示状态，由于递归算法执行中系统栈保存了递归调用的值参、局部变量和返回地址。

所以在递归算法中一次递归调用后会自动恢复该次递归调用前的状态。

递归算法的时空分析

递归算法执行过程不同于非递归算法，所以其时空分析也不同于非递归算法。

非递归算法分析是定长时空分析。

递归算法分析就是变长时空分析。

递归算法的时间分析

递归算法的空间分析

递归算法分析

递归算法设计的步骤

设计求解问题的递归模型。

转换成对应的递归算法。

　求递归模型的步骤如下：

采用递归算法求整数数组a[0..n-1]中的最小值。

基于递归数据结构的递归算法设计

假设有一个不带头结点的单链表p，完成以下两个算法设计：

（1）设计一个算法正向输出所有结点值。

（2）设计一个算法反向输出所有结点值。

(1)正向输出

(2)反向输出

基于归纳方法的递归算法设计

通过对求解问题的分析归纳来转换成递归方法求解（如皇后问题等）。

关键是对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体，而其中最重要的又是假设出“合理”的小问题。

例子：若算法pow(x，n)用于计算xn（n为大于1的整数）。完成以下任务：

（1）采用递归方法设计pow(x，n)算法。

（2）问执行pow(x，10)发生几次递归调用？求pow(x,n)对应的算法复杂度是多少？

例子：创建一个n阶螺旋矩阵并输出。例如，n=4时的螺旋矩阵如下：

答案：

例子：采用递归算法求解迷宫问题，并输出从入口到出口的所有迷宫路径。