C语言中递归的经典算法

来自软件实验室
跳转至: 导航搜索

在刚接触到C语言中的递归时,真的感觉有点抽象,但换种方式去了解它或许会更容易些。我是把它看成了数学中经常用的函数f(x)=f(x-1)-f(x-2)等递归函数,其实道理是一样的,但经历了高中的题海战术后,对数学算法大家应该都更熟悉些。理解归理解,我们还是要学会在程序中用,那就需要“题海”了。在这里呢我整理了一些经典算法,程序都是运行过的。希望与君共勉。 在刚接触到C语言中的递归时,真的感觉有点抽象,但换种方式去了解它或许会更容易些。我是把它看成了数学中经常用的函数f(x)=f(x-1)-f(x-2)等递归函数,其实道理是一样的,但经历了高中的题海战术后,对数学算法大家应该都更熟悉些。理解归理解,我们还是要学会在程序中用,那就需要“题海”了。在这里呢我整理了一些经典算法,程序都是运行过的。希望与君共勉。

  1. 辗转相除法求最大公约数

步骤如下:先用小的一个数除大的一个数,得第一个余数;再用第一个余数除小的一个数,得第二个余数;又用第二个余数除第一个余数,得第三个余数;这样逐次用后一个数去除前一个余数,直到余数是0为止。那么,最后一个除数就是所求的最大公约数(如果最后的除数是1,那么原来的两个数是互质数)

int yueshu (int a,int b) {

   int temp;
   if(a<b)
   {
       temp=a;
       a=b;
       b=temp;
   }
   if(a%b==0)
      return b;
   else
       return yueshu(b,a%b);

}

  1. 求阶乘

n!=n*(n-1)*(n-2)*(n-3)*....*1

int jiecheng (int n) {

   if(n==0 || n==1)
       return 1;
   else
      return jiecheng(n-1)*n;

}

  1. 翻转字符串

void revers(char *cs) {

   if (*cs)
   {
       revers(cs + 1);
       putchar(*cs);
   }

}

  1. 十进制转化为二进制

除二取余,最后逆序排列

void shier(int num)

{
   int i = num % 2;
   if (num > 1) shier(num / 2);
       putchar(i ? '1' : '0');
              //putchar('0' + i);  /* 可代替上面一句 */

}

  1. 河内塔问题

有A、B、C三根柱子。A上堆放了n个盘子,每个盘子都比它下面的盘子小一些。现在要把盘子全部搬到C上去,条件是每次只能搬动一个盘子,而且任何时候都不能放在比它小的盘子上面(显然,必须用到B作为中转)。怎么搬动这些盘子呢?

void hanoi(int n,char A,char B,char C) {

   if(n==1)
   {
       printf("Move sheet %d from %c to %c\n",n,A,C);
   }
   else
   {
       hanoi(n-1,A,C,B);
       printf("Move sheet %d from %c to %c\n",n,A,C);
       hanoi(n-1,B,A,C);
   }

}

如果能理解这些,那递归算法就算掌握了。在学习中使用效果更好哦~