递归程序设计

1、递归的定义

递归是指在函数定义中有吊影函数自身的方法，若函数p函数定义中又调用了函数p，这种递归称为直接递归，若p函数调用函数q, 函数q 有调用了函数p,称之为间接递归。

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

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

2、递归的次数必须是有限的。

3、必须有结束递归的天界来终止递归

2、何时使用递归

1、定义是递归的

有许多数学公式，数列和概念的定义是递归的，如 n! 、斐波那契数列

2、数据结构是递归的

比如单链表二叉树

struct List{
   	int data;	struct List *next;};struct Tree{
   	int data;	struct Tree *left;	struct Tree *right;};

3、问题的求解方案是递归的

有些问题的求解方法是递归的，比如汉诺塔问题。

3、递归的模型

在解决递归问题的时候，先建立一个递归的模型，如：

f(n) = 1  当（n = 1）时f(n) = nf(n-1) 当（n > 1）时

4、递归算法的执行过程

在这里先不考虑求解问题的效率，比如斐波那契数列

如上图，在求f(5)的时候，先求f(4) 和 f(3)

要求f (4) 先求f(3) 和 f(2)

要求f(3) 先求 f(2) 和 f(1)

f(2) 和 f(1) 已知，再往上求 f(3) f(4) f(5)

先向下递归，再向上求解，在递归的过程中，调用函数自身，函数的调用会有系统栈帧的开辟。

从上可以得出：

1、递归的执行是通过系统栈来实现的。

2、每次递归就需要将参数，局部变量和返回地址作为一个栈元素入栈一次，入栈的次数越多，递归的深度越深。

3、每遇到递归的出口，就会出栈一次，直到栈中的元素为空为止。

递归设计解题过程

n皇后问题，如果不了解n皇后，可自行查询一下具体的细节，这里不多做说明。

#include 
   
    #include 
    
     #define MAX 20//p[i]表示 第i个皇后的位置int p[MAX];//打印函数void Display(int n){
       int i = 1;    for(; i <= n; i++)    {
           printf("%d ",p[i]);    }    printf("\n");}//判断j位置是否满足要求int Place(int i,int j){
       int k = 1;    for(k = 1; k < i; k++)    {
           if(p[k] == j || abs(p[k]-j) == abs(i-k))        {
               return 0;        }    }    return 1;}void Queen(int i,int n){
   	//i表示当前需要安排第几个皇后，	//如果最后一个已经放到了相应的位置，则直接输出，递归出来    if(i > n)    {
           Display(n);    }    int j = 1;    //从 1 开始 遍历 找到合法的位置    for(; j <= n; j++)    {
           if(Place(i,j) == 1)        {
               p[i] = j;            //找到一个合法的位置，递归开始找下一个皇后的位置            Queen(i+1,n);        }    }}int main(){
       Queen(1,4);    return 0;}

结语

这里先将递归的基本概念以及求解方法介绍一下，对问题的求解篇幅不大，以后继续更新递归求解问题的方法。

转载地址：http://stnwi.baihongyu.com/

你可能感兴趣的文章