算法之递归

[jyzwf]

递归算法在实际应用中很常见，递归的就是把一个大问题分割为几个相似的简单的小问题，在方法里调用自身，关键点有点：

1. 每次调用时，在问题规模上都要有所减小（一般是减半）
2. 相邻两次重复调用时，前一次一般要为后一次做准备（通常前一次的输出是后一次的输入）
3. 必须要有明确的 递归结束条件，否则为无限循环

使用递归能减少我们的代码量，但是递归的运行效率是较低的，在递归调用过程中，系统为每一层的返回点、局部变量等开辟栈来存储，递归次数过多容易导致栈溢出。

下面是一个使用递归进行进制转换的demo：

code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void convto(char *s,int n,int b)
{
       char bit[] = ("0123456789ABCDEF");
       int len;
       if(n == 0)
       {
              strcpy(s,"");
              return;
       }

       convto(s,n/b,b);
       len = strlen(s);
       s[len] = bit[n%b];
       s[len+1]='\0';
}


int main()
{
    char s[80];
    int i,base,old;
    printf("请输入十进制数：");
    scanf("%d",&old);
    printf("请输入转换的进制：");
    scanf("%d",&base);
    convto(s,old,base);
    printf("%s\n",s);
    getch();
    return 0;
}

result