（一）递归算法设计技术（学习笔记一）

（一）递归的定义

递归：在函数的定义中又调用函数自身的方法。分为直接递归和间接递归。

直接递归：在函数p定义中调用函数p。

间接递归：在函数p定义中调用q函数，而函数q定义中又调用了p函数。

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

求n！（n为正整数）

1 int fun(int n)
2 {
3     if(n == 1)
4         return 1;
5     else
6         return(fun(n-1)*n);
7 }

代码中，fun(n) 调用了 fun(n-1) ，属于直接递归；又由于递归调用是最后一句语句，故也属于尾递归。

（二）什么时候是用递归

定义是递归的：有许多数学公式、数列和概念的定义是递归的，对于这些问题的求解过程，可以将递归定义直接转化为对应的递归算法。

数据结构是递归的：如单链表、二叉树，有些存储数据的数据结构是递归的，可以采用递归方法解决此类问题。

某些问题的求解方法是递归的也可以用递归调用方法快速解决问题。

分析二叉树的二叉链存储结构的递归性，设计求非空二叉链bt中所有结点值之和的递归算法，假设二叉链的 data 域为 int 型。

解：二叉树采用二叉链存储结构，其结点类型定义如下：

typedef struct BNode
{
    int data;
    struct BNode *lchild, *rchild;
}BTNode;                                      //二叉链结点类型

求非空二叉链 bt 中所有结点值之和的递归算法如下：

int Sumbt(BTNode *bt)
{
    if(bt->lchild == NULL && bt->rchild == NULL)
        return bt->data;
    else
        return Sumbt(bt->lchild) + Sumbt(bt->rchild) + bt->data;
}

（三）递归模型

递归模型是递归算法的抽象，它反映了一个递归问题的递归结构。这么说有点抽象了，让我们来看看是怎么回事叭！

一般来说，一个递归模型由递归出口和递归体两部分组成，前者确定递归到什么时候结束，即指出明确的结束条件；后者确定递归求解时的递推关系。

一般的递归模型如下：

f(s1) = m1
f(sn) = g(f(sn-1),cn-1)

实际上，递归思路是把一个不好直接解决的“大问题”化为一个或几个“小问题”，再将“小问题”进一步分解成更小的“小问题”来解决。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即过程与环境都相似。

我们再来把求解n！来分析一遍

n! 的递归体可以看成 f(n) = g(f(n-1),n) ，其中 g(x,y) = x*y ；而当 n = 1 时，就不再调用递归函数了，直接返回 1 。

（四）递归算法的执行过程

在执行递归函数时会直接调用自身，但如果仅有这种操作，将会出现由于无休止的调用而陷入的死循环。因此，一个正确的递归函数虽然每次调用的是相同的代码，但它的参数、输入数据等均有变化，并且在正常的情况下随着调用的不断深入必定会出现调用到某一层的函数时不再执行递归调用而终止函数的执行，即遇到递归出口。

归纳起来，递归调用的实现是分两步进行的。第一步是分解过程，即用递归体将“大问题”分解成“小问题”，直到遇到递归出口为止，然后进行第二步的求值过程，即已知“小问题”计算“大问题”。

那现在我们来看看如何用递归方法解决Fibonacci数列问题

Fibonacci数列定义如下：

Fib(n) = 1                         当 n = 1 时
Fib(n) = 1                         当 n = 2 时
Fib(n) = Fib(n-1) + Fib(n-2)       当 n > 2 时

对应的递归算法如下：

int Fib(int n)
{
    if(n == 1 || n == 2)
        return 1;
    else
        return Fib(n-1) + Fib(n-2);
}

以上就是“递归算法设计技术”的第一部分笔记，欢迎各位读者阅读！

注：“算法设计与分析”这一门课使用的计算机语言为C语言

（一）递归算法设计技术（学习笔记一）

相关推荐