C語言程序中遞歸算法的使用實(shí)例教程
更新時(shí)間：2016年04月25日 15:28:13 作者：wuyudong
這篇文章主要介紹了C語言程序中遞歸算法的使用實(shí)例教程,遞歸經(jīng)常被用來進(jìn)行階乘和比較大小等計(jì)算工作,文中舉的都是一些基礎(chǔ)的例子,需要的朋友可以參考下
1.問題：計(jì)算n！
數(shù)學(xué)上的計(jì)算公式為：
n！=n×(n-1)×(n-2)……2×1
使用遞歸的方式，可以定義為：
以遞歸的方式計(jì)算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 遞歸完成
以遞歸方式實(shí)現(xiàn)階乘函數(shù)的實(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.原理
下面來詳細(xì)分析遞歸的工作原理
先看看C語言中函數(shù)的執(zhí)行方式，需要了解一些關(guān)于C程序在內(nèi)存中的組織方式：
堆的增長方向?yàn)閺牡偷刂返礁叩刂废蛏显鲩L，而棧的增長方向剛好相反（實(shí)際情況與CPU的體系結(jié)構(gòu)有關(guān)）。
當(dāng)C程序中調(diào)用了一個(gè)函數(shù)時(shí)，棧中會(huì)分配一塊空間來保存與這個(gè)調(diào)用相關(guān)的信息，每一個(gè)調(diào)用都被當(dāng)作是活躍的。棧上的那塊存儲(chǔ)空間稱為活躍記錄或者棧幀
棧幀由5個(gè)區(qū)域組成：輸入?yún)?shù)、返回值空間、計(jì)算表達(dá)式時(shí)用到的臨時(shí)存儲(chǔ)空間、函數(shù)調(diào)用時(shí)保存的狀態(tài)信息以及輸出參數(shù)，參見下圖：
可以使用下面的程序來檢驗(yàn):
#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;
}
棧是用來存儲(chǔ)函數(shù)調(diào)用信息的絕好方案，然而棧也有一些缺點(diǎn)：
棧維護(hù)了每個(gè)函數(shù)調(diào)用的信息直到函數(shù)返回后才釋放，這需要占用相當(dāng)大的空間，尤其是在程序中使用了許多的遞歸調(diào)用的情況下。除此之外，因?yàn)橛写罅康男畔⑿枰４婧突謴?fù)，因此生成和銷毀活躍記錄需要消耗一定的時(shí)間。我們需要考慮采用迭代的方案。幸運(yùn)的是我們可以采用一種稱為尾遞歸的特殊遞歸方式來避免前面提到的這些缺點(diǎn)。
3.斐波那契數(shù)列
#include <stdio.h>
int fibonacci(int a){//fibonacci數(shù)列，第一二項(xiàng)為1；后面的每一項(xiàng)為前兩項(xiàng)之和
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.四個(gè)數(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.猴子吃桃
每天吃一半再多吃一個(gè)，第十天想吃時(shí)候只剩一個(gè)，問總共有多少：
int chitao(int i){//猴子吃桃，每天吃一半再多吃一個(gè)，第十天想吃時(shí)候只剩一個(gè)
if(i == 10){
return 1;
}else{
return (chitao(i + 1) + 1) * 2;
}
}
相關(guān)文章
C語言函數(shù)是一種函數(shù)，用來編譯C語言，一般包括字符庫函數(shù)，數(shù)學(xué)函數(shù)，目錄函數(shù)，進(jìn)程函數(shù)，診斷函數(shù)，操作函數(shù)等，宏在C語言中是一段有名稱的代碼片段。無論何時(shí)使用到這個(gè)宏的時(shí)候，宏的內(nèi)容都會(huì)被這段代碼替換掉2022-04-04
這篇文章主要為大家介紹了C語言算法積累加tag的循環(huán)隊(duì)列的解題思路，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
VC實(shí)現(xiàn)五子棋游戲的一個(gè)算法示例
這篇文章主要介紹了VC實(shí)現(xiàn)五子棋游戲的一個(gè)算法示例,對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的朋友有一定的借鑒價(jià)值,需要的朋友可以參考下2014-08-08
C++實(shí)現(xiàn)對(duì)象化的矩陣相乘小程序
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)對(duì)象化的矩陣相乘小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
單向鏈表特點(diǎn)是鏈表的鏈接方向是單向的，訪問要通過順序讀取從頭部開始。鏈表是使用指針構(gòu)造的列表，是由一個(gè)個(gè)結(jié)點(diǎn)組裝起來的，又稱為結(jié)點(diǎn)列表。其中每個(gè)結(jié)點(diǎn)都有指針成員變量指向列表中的下一個(gè)結(jié)點(diǎn)，head指針指向第一個(gè)結(jié)點(diǎn)稱為表頭，而終止于最后一個(gè)指向nuLL的指針2021-11-11
這里主要介紹了C語言的轉(zhuǎn)義字符的知識(shí),并附有示例代碼,以便理解,希望對(duì)學(xué)習(xí) C語言的同學(xué)有所幫助2016-07-07
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡易撲克牌游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
這篇文章主要介紹了C語言signed關(guān)鍵字的詳細(xì)使用，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
的相關(guān)資料
這篇文章主要介紹了LZ77壓縮算法原理的理解的相關(guān)資料,數(shù)據(jù)壓縮是一個(gè)減小數(shù)據(jù)存儲(chǔ)空間的過程，目前被應(yīng)用在軟件工程的各個(gè)地方，了解其一些原理，方便我們更好的甄選壓縮方案,需要的朋友可以參考下2017-08-08
Base64是一種很常用的編碼方式，利用它可以將任何二進(jìn)制的字符編碼到可打印的64個(gè)字符之中， 這樣，不管是圖片，中文文本等都可以編碼成只有ASCII的純文本。2015-11-11