C語言程序中遞歸算法的使用實例教程

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

1.問題：計算n！
數(shù)學(xué)上的計算公式為：

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　　　　　　　　　　　　　　　　 遞歸完成

以遞歸方式實現(xiàn)階乘函數(shù)的實現(xiàn)：

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語言中函數(shù)的執(zhí)行方式，需要了解一些關(guān)于C程序在內(nèi)存中的組織方式：

堆的增長方向為從低地址到高地址向上增長，而棧的增長方向剛好相反（實際情況與CPU的體系結(jié)構(gòu)有關(guān)）。

當C程序中調(diào)用了一個函數(shù)時，棧中會分配一塊空間來保存與這個調(diào)用相關(guān)的信息，每一個調(diào)用都被當作是活躍的。棧上的那塊存儲空間稱為活躍記錄或者棧幀

棧幀由5個區(qū)域組成：輸入?yún)?shù)、返回值空間、計算表達式時用到的臨時存儲空間、函數(shù)調(diào)用時保存的狀態(tài)信息以及輸出參數(shù)，參見下圖：

可以使用下面的程序來檢驗:

#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傳入?yún)?shù)地址\n");
  printf("in max: 0x%08x\n\n",&i);
  printf("打印max函數(shù)中靜態(tài)變量地址\n");
  printf("0x%08x\n",&n1_max); 
//打印各本地變量的內(nèi)存地址
  printf("0x%08x\n",&n2_max);
  printf("0x%08x\n\n",&n3_max);
  printf("打印max函數(shù)中局部變量地址\n");
  printf("0x%08x\n",&m1); 
//打印各本地變量的內(nèi)存地址
  printf("0x%08x\n",&m2);
  printf("0x%08x\n\n",&m3);
  printf("打印max函數(shù)中malloc分配地址\n");
  printf("0x%08x\n\n",p_max); 
//打印各本地變量的內(nèi)存地址
  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èi)存地址\n");
  printf("0x%08x\n",&g1); 
//打印各全局變量的內(nèi)存地址
  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("打印各靜態(tài)變量的內(nèi)存地址\n");
  printf("0x%08x\n",&s1); 
//打印各靜態(tài)變量的內(nèi)存地址
  printf("0x%08x\n",&s2);
  printf("0x%08x\n\n",&s3);
  printf("打印各局部變量的內(nèi)存地址\n");
  printf("0x%08x\n",&v1); 
//打印各本地變量的內(nèi)存地址
  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("打印子函數(shù)起始地址\n");
  printf("max: 0x%08x\n\n",max);
  return 0;
}

棧是用來存儲函數(shù)調(diào)用信息的絕好方案，然而棧也有一些缺點：

棧維護了每個函數(shù)調(diào)用的信息直到函數(shù)返回后才釋放，這需要占用相當大的空間，尤其是在程序中使用了許多的遞歸調(diào)用的情況下。除此之外，因為有大量的信息需要保存和恢復(fù)，因此生成和銷毀活躍記錄需要消耗一定的時間。我們需要考慮采用迭代的方案。幸運的是我們可以采用一種稱為尾遞歸的特殊遞歸方式來避免前面提到的這些缺點。

3.斐波那契數(shù)列

#include <stdio.h> 
 
int fibonacci(int a){//fibonacci數(shù)列，第一二項為1；后面的每一項為前兩項之和 
  if (a == 1 || a == 2) 
  { 
    return 1; 
  }else{ 
    return fibonacci(a - 1) + fibonacci(a - 2); 
  } 
} 
 
void main(){ 
  printf("%d\n",fibonacci(40)); 
}

4.遞歸將整形數(shù)字轉(zhuǎn)換為字符串

#include <stdio.h> 
 
int toString(int i, char str[]){//遞歸將整形數(shù)字轉(zhuǎn)換為字符串 
  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.四個數(shù)找最大

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; 
  } 
}

上一篇：C++實現(xiàn)簡單的HTTP服務(wù)器

欄目：C語言

下一篇：C++簡單QQ程序服務(wù)器端的實現(xiàn)代碼

本文標題：C語言程序中遞歸算法的使用實例教程

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/2350.html

更多C語言

雷火电竞-中国电竞赛事及体育赛事平台

C語言

C語言程序中遞歸算法的使用實例教程

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機閱讀