溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

深入淺析C語言中的遞歸

發(fā)布時(shí)間：2020-11-19 15:04:37 來源：億速云 閱讀：162 作者：Leah 欄目：開發(fā)技術(shù)

深入淺析C語言中的遞歸？相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

什么是遞歸？

要說到遞歸如果不說棧的話，我覺得有點(diǎn)不合適，遞歸特點(diǎn)就是不斷的調(diào)用同一個(gè)函數(shù)，如果這個(gè)函數(shù)沒有一個(gè)遞歸界限，那么就是死循環(huán)了，所以討論遞歸，就必須要討論遞歸的界限，就是限定這個(gè)遞歸調(diào)用多少次。

我們看一個(gè)例子

#include "stdio.h"

int digui(unsigned long count )
{
 if(count > 0){
 count --;
 printf("%d \n",count);
 digui(count);
 }
 return 1;
}

int main()
{
 digui(10);
 return (100);
}

這個(gè)遞歸函數(shù)的限定判讀是

if(count > 0){

所以他的調(diào)用順序可以用這個(gè)圖示來說明

深入淺析C語言中的遞歸

這個(gè)過程叫做遞去，也就是壓棧的過程，既然有壓棧的過程，那么就有出棧的過程，出棧的過程就是

if(count > 0){

判斷不成功后，就會(huì)出棧了。如下圖所示

深入淺析C語言中的遞歸

一共能執(zhí)行多少次遞歸？

我們上面說到了，既然遞歸使用了棧，那么系統(tǒng)的棧的大小肯定是有極限的，不可能系統(tǒng)給你分配無極限的棧的大小，我看一些文章說棧大小是64K。

還是上面那個(gè)例子，我把傳入數(shù)據(jù)設(shè)置為很大執(zhí)行看看。

#include "stdio.h"

int tigui(unsigned long count )
{
 if(count > 0){
 count --;
 printf("%d \n",count);
 tigui(count);
 }
 return 1;
}

int main()
{
 tigui(900000);
 return (100);
}

執(zhí)行結(jié)果

深入淺析C語言中的遞歸

所以說遞歸次數(shù)肯定是有限定的了。

遞歸求階乘

使用遞歸求階乘是很經(jīng)典的方法，我們看一下代碼。

#include<stdio.h>
int fact(unsigned long n); //聲明階乘fact函數(shù)
int main(){
 unsigned long x;
 scanf("%d",&x);
 x = fact(x);//調(diào)用函數(shù)返回int值
 printf("%ld\n",x);
 return (0);
}
int fact(unsigned long n){//定義階乘函數(shù)
 if(n==1) return 1;//輸入的參數(shù)是1，直接返回1
 else return n*fact(n-1);//遞歸算法
}

執(zhí)行結(jié)果

深入淺析C語言中的遞歸

單看代碼我覺得還是有點(diǎn)拗口 我們看個(gè)圖片來看他的調(diào)用，假設(shè)我們要求的是 5 的階乘

深入淺析C語言中的遞歸

遞歸和漢諾塔

漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

深入淺析C語言中的遞歸

如果是這樣的漢諾塔，我覺得應(yīng)該每個(gè)人都覺得很簡單吧，只需要三步就可以完成移動(dòng)。

1、把小圓盤放到第三根柱子上

2、把中圓盤放到第二根柱子上

3、把小圓盤放到第二根柱子上

4、把大圓盤放到第三根柱子上

5、把小圓盤放到第一根柱子上

6、把中圓盤放到第三根柱子上

7、把小圓盤放到第三根柱子上

如圖所示

深入淺析C語言中的遞歸

剖析我們上面是細(xì)分的方法，移動(dòng)的核心思想分為三步。

1、把第一個(gè)柱子上的n-1圓盤移動(dòng)到第二個(gè)柱子上。

2、把第一個(gè)柱子的第n個(gè)圓盤移動(dòng)到第三個(gè)柱子上。

3、把第二個(gè)柱子的n-1個(gè)圓盤移動(dòng)到第三個(gè)柱子。

所以遞歸就出現(xiàn)了

1、把第一個(gè)柱子上的n-1圓盤移動(dòng)到第二個(gè)柱子上「遞歸實(shí)現(xiàn)」。

2、把第一個(gè)柱子的第n個(gè)圓盤移動(dòng)到第三個(gè)柱子上。

3、把第二個(gè)柱子的n-1個(gè)圓盤移動(dòng)到第三個(gè)柱子「遞歸實(shí)現(xiàn)」。

C語言代碼實(shí)現(xiàn)

#include <stdio.h>
#include <windows.h>
void Hanoi(int n, char a,char b,char c);
void Move(int n, char a, char b);
int count;
int main()
{
 int n=8;
 printf("漢諾塔的層數(shù):\n");
 scanf(" %d",&n);
 Hanoi(n, 'A', 'B', 'C');
 printf("Exiting main...\n");
 return 0;
}
void Hanoi(int n, char a, char b, char c)
{
 if (n == 1)
 {
  Move(n, a, c);
 }
 else
 {
  Hanoi(n - 1, a, c, b);/*把 n-1 從 a 柱子放到 b 柱子上面*/
  Move(n, a, c);  /*把 n 從 a 移動(dòng)到 c 上*/
  Hanoi(n - 1, b, a, c);/*把n - 1 通過 a 的輔助作用 從 b 移動(dòng)到 c 上*/
 }
}
void Move(int n, char a, char b)
{
 count++;
 printf("第%d次移動(dòng) Move %d: 從 %c 位置 移動(dòng)到 %c !\n",count,n,a,b);
}

輸出如圖所示

深入淺析C語言中的遞歸

加強(qiáng)版修改

加強(qiáng)了下軟件寫法，好好看代碼，寫的有點(diǎn)太快，沒細(xì)想，后面再完善。

#include <stdio.h>

/*柔性數(shù)組*/
typedef struct _soft_array{
 int len;
 int array[];
}soft_array;

/*漢諾塔結(jié)構(gòu)體*/
typedef struct _hannuo{
 soft_array *p_data;
 char name;
}hannuo;

hannuo * han_a = NULL;
hannuo * han_b = NULL;
hannuo * han_c = NULL;

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c);
void moveiii (int n,hannuo * a,hannuo * c);

int total;

void printf_han_data(hannuo * han)
{
 int i = 0;
 printf("%c: ",han->name);
 /*輸出漢諾塔的數(shù)據(jù)*/
 for(i = 0;i<han->p_data->len;i++)
 {
 printf("%d-",han->p_data->array[i]);
 }
 printf("\n"); 
}


int main()
{
 int i = 0;
 int n = 0;

 scanf(" %d",&n);
 total = n;
 /*定義三個(gè)漢諾塔節(jié)點(diǎn)*/
 han_a = (hannuo *)malloc(sizeof(hannuo));
 han_a->name = 'A';
 han_a->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
 han_a->p_data->len = n;
 
 /*數(shù)據(jù)原來在第一根柱子上*/
 for(i = 0;i<n;i++)
 {
 han_a->p_data->array[i] = i+1;
 }
 printf_han_data(han_a);
 
 /*初始化第二根柱子*/
 han_b = (hannuo *)malloc(sizeof(hannuo));
 han_b->name = 'B';
 han_b->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
 memset(han_b->p_data,0,sizeof(soft_array)+sizeof(int)*n);
 han_b->p_data->len = n;
 printf_han_data(han_b);
 /*初始化第三根柱子*/
 han_c = (hannuo *)malloc(sizeof(hannuo));
 han_c->name = 'C';
 han_c->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
 memset(han_c->p_data,0,sizeof(soft_array)+sizeof(int)*n);
 han_c->p_data->len = n;
 printf_han_data(han_c);
 printf("------------------------\n");
 hannoiii(n,han_a,han_b,han_c);
 

 printf("\n");
 return 0;
}

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c)
{
 if(n == 1)
 {
 a->p_data->array[0] = 0;
 c->p_data->array[0] = 1;
 printf_han_data(han_a);
 printf_han_data(han_b);
 printf_han_data(han_c);
 printf("------------------------\n");
 }
 else
 {
 hannoiii(n - 1, a, c, b);/*把 n-1 從 a 柱子放到 b 柱子上面*/
  moveiii(n, a, c);  /*把 n 從 a 移動(dòng)到 c 上*/
 printf_han_data(han_a);
 printf_han_data(han_b);
 printf_han_data(han_c);
 printf("------------------------\n");
  hannoiii(n - 1, b, a, c);/*把n - 1 通過 a 的輔助作用 從 b 移動(dòng)到 c 上*/
 }
}

void moveiii (int n,hannuo * a,hannuo * c)
{
 int i = 0;
 int tmp = a->p_data->array[n-1];
 a->p_data->array[n-1] = 0;
 #if 1
 c->p_data->array[n-1] = tmp;
 #else
 for(i = 0;i < total;i++)
 {
  if(c->p_data->array[i] == 0){
   c->p_data->array[i] = tmp;
   break;
  }
 }
 #endif
}

深入淺析C語言中的遞歸

看完上述內(nèi)容，你們掌握深入淺析C語言中的遞歸的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手