C语言程序中递归算法的使用实例教程

1.问题：计算n！
数学上的计算公式为：

n！=n×(n-1)×(n-2)……2×1

使用递归的方式，可以定义为：

以递归的方式计算4！

F(4)=4×F(3)　　　　　　　　　　　　递归阶段

F(3)=3×F(2)

F(2)=2×F(1)

F(1)=1　　终止条件

F(2)=(2)×(1)　　　 回归阶段

F(3)=(3)×(2)

F(4)=(4)×(6)

24　　　　　　　　　　　　　　　　 递归完成

以递归方式实现阶乘函数的实现：

int fact(int n) {
  if(n < 0)
    return 0;
  else if (n == 0 || n == 1)
    return 1;
  else
    return n * fact(n - 1);
}

2.原理
下面来详细分析递归的工作原理

先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：

堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。栈上的那块存储空间称为活跃记录或者栈帧

栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：

可以使用下面的程序来检验:

#include <stdio.h>
int g1=0, g2=0, g3=0;
int max(int i)
{
  int m1 = 0, m2, m3 = 0, *p_max;
  static n1_max = 0, n2_max, n3_max = 0;
  p_max = (int*)malloc(10);
  printf("打印max程序地址\n");
  printf("in max: 0x%08x\n\n",max);
  printf("打印max传入参数地址\n");
  printf("in max: 0x%08x\n\n",&i);
  printf("打印max函数中静态变量地址\n");
  printf("0x%08x\n",&n1_max);
//打印各本地变量的内存地址
  printf("0x%08x\n",&n2_max);
  printf("0x%08x\n\n",&n3_max);
  printf("打印max函数中局部变量地址\n");
  printf("0x%08x\n",&m1);
//打印各本地变量的内存地址
  printf("0x%08x\n",&m2);
  printf("0x%08x\n\n",&m3);
  printf("打印max函数中malloc分配地址\n");
  printf("0x%08x\n\n",p_max);
//打印各本地变量的内存地址
  if(i) return 1;
  else return 0;
}
int main(int argc, char **argv)
{
  static int s1=0, s2, s3=0;
  int v1=0, v2, v3=0;
  int *p;
  p = (int*)malloc(10);
  printf("打印各全局变量(已初始化)的内存地址\n");
  printf("0x%08x\n",&g1);
//打印各全局变量的内存地址
  printf("0x%08x\n",&g2);
  printf("0x%08x\n\n",&g3);
  printf("======================\n");
  printf("打印程序初始程序main地址\n");
  printf("main: 0x%08x\n\n", main);
  printf("打印主参地址\n");
  printf("argv: 0x%08x\n\n",argv);
  printf("打印各静态变量的内存地址\n");
  printf("0x%08x\n",&s1);
//打印各静态变量的内存地址
  printf("0x%08x\n",&s2);
  printf("0x%08x\n\n",&s3);
  printf("打印各局部变量的内存地址\n");
  printf("0x%08x\n",&v1);
//打印各本地变量的内存地址
  printf("0x%08x\n",&v2);
  printf("0x%08x\n\n",&v3);
  printf("打印malloc分配的堆地址\n");
  printf("malloc: 0x%08x\n\n",p);
  printf("======================\n");
  max(v1);
  printf("======================\n");
  printf("打印子函数起始地址\n");
  printf("max: 0x%08x\n\n",max);
  return 0;
}

栈是用来存储函数调用信息的绝好方案，然而栈也有一些缺点：

栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。我们需要考虑采用迭代的方案。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。

3.斐波那契数列

#include <stdio.h> 

int fibonacci(int a){//fibonacci数列，第一二项为1；后面的每一项为前两项之和
  if (a == 1 || a == 2)
  {
    return 1;
  }else{
    return fibonacci(a - 1) + fibonacci(a - 2);
  }
} 

void main(){
  printf("%d\n",fibonacci(40));
}

4.递归将整形数字转换为字符串

#include <stdio.h> 

int toString(int i, char str[]){//递归将整形数字转换为字符串
  int j = 0;
  char c = i % 10 + '0';
  if (i /= 10)
  {
    j = toString(i, str) + 1;
  }
  str[j] = c;
  str[j + 1] = '\0';
  return j;
} 

void main(){
  char str[100];
  int i;
  printf("enter a integer:\n");
  scanf("%d",&i);
  toString(i,str);
  puts(str);
}

5.汉诺塔

#include <stdio.h> 

void hanoi(int i,char x,char y,char z){
  if(i == 1){
    printf("%c -> %c\n",x,z);
  }else{
    hanoi(i - 1,x,z,y);
    printf("%c -> %c\n",x,z);
    hanoi(i - 1,y,x,z);
  }
} 

void main(){
  hanoi(10,'A','B','C');
}

6.四个数找最大

int max(int a, int b, int c, int d){
  if(a > b && a > c && a > d){
    return a;
  }else{
    max(b,c,d,a);
  }
}

7.猴子吃桃
每天吃一半再多吃一个，第十天想吃时候只剩一个，问总共有多少：

int chitao(int i){//猴子吃桃，每天吃一半再多吃一个，第十天想吃时候只剩一个
  if(i == 10){
    return 1;
  }else{
    return (chitao(i + 1) + 1) * 2;
  }
}