Chinaunix首页 | 论坛 | 博客
  • 博客访问: 332985
  • 博文数量: 78
  • 博客积分: 2536
  • 博客等级: 少校
  • 技术积分: 600
  • 用 户 组: 普通用户
  • 注册时间: 2008-04-29 01:50
文章分类

全部博文(78)

文章存档

2011年(1)

2010年(17)

2009年(52)

2008年(8)

我的朋友

分类: C/C++

2009-10-26 18:33:12

递归是种思想,不是算法。
一个算法,你用递归去实现,它就是递归算法;你用循环去实现,它就是非递归算法。递归与循环一一对应,大多数编程语言都支持循环,但不一定支持递归。
一个大问题,分解成类似的小问题,递归只用一句话就能描述这些“重复工作”,代码那叫一个简单!想想这句话的威力都觉得很牛B!
递归算法简单而又经典的例子有:n!、Fibonacci、Hanoi、回溯、树遍历、图搜索。敲代码的时候,递归反映为func()里调用func(),当然传入的形参是不一样的,而且递归必须要有exit door(不然递归到哪天才是个头呀,一直往深了递归,stack非给溢出不可,通常100层以上的递归就会overflow了)。递归算法其实是低效的,每次递归到下一层,系统都要为这一层记录返回地址、局部变量开辟stack空间,返回上一层的时候系统还要花时间删掉这些东东,系统真累!
下面看一下Honoi示例:
#include
 
void move(char x,char y)
{
       printf("%c-->%c\n",x,y);
}
main()
{
       int m;
       scanf("%d",&m);
       hanoi(m,'1','2','3');
}
 void hanoi(int n,char one,char two,char three)
{
       if(n==1)move(one,three);
       else
       {
              hanoi(n-1,one,three,two);
              move(one,three);
              hanoi(n-1,two,one,three);
       }
}
/*
n>=2时, 移动分三步:
step1: 把A上的n-1个圆盘移到B上;
Step2: 把A上的一个圆盘移到C上;
Step3: 把B上的n-1个圆盘移到C上;
*/
 
 
循环与递归是一对一的,下面给出最简单的示例:
int n=5;
int a[]={1,2,3,4,5};
 
int main()
{
       int sum=0;
       for(int i=0;i
              sum+=a[i];
 
       sum=sum2(n-1);
}
 int sum2(int n)
{
       if(n<0)
              return 0;
       else
              return sum2(n-1)+a[n];
}
 
 
 
假如你把算法设计成了递归形式,再用stack去模拟消递归,效果不一定就好,你只是做了系统做的事情。所以,不要盲目相信非递归算法就比递归算法效率高,如果消递归技术不好,效率还不及原来的呢。
 
做些练习巩固一下吧,用递归的方法完成:
1. 求数组中的最大数
2. 求n个整数的积
3. 求n个整数的平均值
4. 求n个自然数的最大公约数与最小公倍数
5. 有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
6. 已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
第6题解答:
#include
 
int main()
{
      int n;
      int a[]={1,1,2};
 
      scanf("%d",&n);
      int tem=sum(n);
      printf("%d\n",tem);
      return 0;
}
 int sum(int n)
{
      if(n<3)
           return a[n];
      else
           return sum(n-1)+sum(n-2)+sum(n-3);
}
 
 
 
Ø         递归生成所有全排列
实现1:
#include
#include
#include
bool used[100];
char a[100],n,c[100];
int main(){
    scanf("%d",&n);
    scanf("%s",c);
    f(0);
    system("Pause");
    return 0;
}
 int f(int dep){
    if(dep>=n){
        for(int i = 0;i            printf("%c ",a[i]);
        printf("\n");
    }
    else{
        for(int i = 0;i            if(!used[i]){
                a[dep] = c[i];
                used[i] = true;
                f(dep+1);
                used[i] = false;
            }
    }
}
 
12345,12354,12435,12453,…,54321
 
实现2:
设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p),pn = p - {rn}。因此Perm(p) = r1Perm(p1), r2Perm(p2), r3Perm(p3), ... , rnPerm(pn)。
#include  
 
int n = 0; 
 
void swap(int *a, int *b)
{    
    int m;    
    m = *a;    
    *a = *b;    
    *b = m;
 
int main()
{    
    int list[] = {1, 2, 3, 4, 5};    
    perm(list, 0, 4);    
    printf("total:%d\n", n);    
    return 0;

 void perm(int list[], int k, int m)
{    
    int i;    
    if(k > m)    
    {         
        for(i = 0; i <= m; i++)            
            printf("%d ", list[i]);        
        printf("\n");        
        n++;    
    }    
    else    
    {        
        for(i = k; i <= m; i++)        
        {            
            swap(&list[k], &list[i]);            
            perm(list, k + 1, m);            
            swap(&list[k], &list[i]);        
        }    
    }
}
 
 
并不是严格字典序的哦,例如12345,12354,12435,12453,“12543,12534”

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/iJuliet/archive/2009/05/11/4169389.aspx
 
阅读(1289) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~