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; } } 新聞熱點
疑難解答
圖片精選
