快捷導(dǎo)航

C語(yǔ)言遞歸系列的深入總結(jié)

更新時(shí)間：2021年02月08日 14:25:20 作者：daener

這篇文章主要給大家總結(jié)介紹了關(guān)于C語(yǔ)言遞歸系列的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

遞歸

什么是遞歸

遞歸簡(jiǎn)而言之就是函數(shù)自己調(diào)用自己如圖所示

但是遞歸并不是簡(jiǎn)簡(jiǎn)單單的自己調(diào)用自己的過(guò)程它分為傳遞和回歸，傳遞就是橙色箭頭回歸則是黑色箭頭這就是遞歸
以計(jì)算階乘為例，假設(shè)我們輸入6 計(jì)算6的階乘為例

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int factorial(int x) //遞歸體函數(shù)
{
	if (x == 1)
	{
		return 1; 
	}
	return x * (factorial(x - 1));
}
int main()
{
	int i = 0;
	scanf("%d", & i);
	int k = factorial(i);
	printf("%d", k);
	return 0;
}

具體實(shí)現(xiàn)過(guò)程如下我們可以很清楚看到先傳遞在歸一就是遞歸

遞歸的特點(diǎn) 結(jié)構(gòu) 缺點(diǎn)

遞歸的本質(zhì)

在傳遞的過(guò)程將問(wèn)題化簡(jiǎn) 歸一的過(guò)程將化簡(jiǎn)的問(wèn)題解決

遞歸的應(yīng)用

(1). 問(wèn)題的定義是按遞歸定義的（Fibonacci函數(shù)，階乘，…）；

(2). 問(wèn)題的解法是遞歸的（有些問(wèn)題只能使用遞歸方法來(lái)解決，例如，漢諾塔問(wèn)題，…）；

(3). 數(shù)據(jù)結(jié)構(gòu)是遞歸的（鏈表、樹等的操作，包括樹的遍歷，樹的深度，…）

遞歸實(shí)戰(zhàn)

階乘

階乘遞歸解法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int factorial(int x) // 遞歸體
{
	if (x == 1)// 函數(shù)出口
	{
		return 1; 
	}
	return x * (factorial(x - 1));//就x！轉(zhuǎn)換成X*((x-1)!) 達(dá)到傳遞化簡(jiǎn)的目的
}
int main()
{
	int i = 0;
	scanf("%d", & i);
	int k = factorial(i);
	printf("%d", k);
	return 0;
}

階乘普通解法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
	int k = 0;
	scanf("%d", &k);
	int i = 0;
	int sum = 1;
	for (i = 1; i < k + 1; i++)
	{
		sum = sum * i; //利用循環(huán)累乘 最后打印
	}
	printf("%d", sum);
	return 0;
}

斐波拉契數(shù)列

斐波拉契數(shù)列即0、1、1、2、3、5、8、13、21、34、………這樣一串?dāng)?shù)字

斐波拉契數(shù)列遞歸解法

遞歸解法通過(guò)數(shù)學(xué)函數(shù)定義可輕松得到他的遞歸體

是當(dāng)n>1時(shí) fib(n-2)+fib(n-1)

遞歸出口就是n=0 返回0，n=1，返回1

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int fib(int x) //第0個(gè)元素為0 第一個(gè)元素為1
{
	if (x == 0)
	{
		return 0;

	}
	else if (x == 1) //出口
	{
		return 1;
	}
	else
		return fib(x - 2) + fib(x - 1); //循環(huán)體 
}


int main()
{
	int k = 0;
	scanf("%d", &k);
	int sum = fib(k);
	printf("%d", sum);
	return 0;
}

斐波拉契數(shù)列普通解法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int fib(int x)
{
	int i = 0;
	int j = 1;
	int k = 0;
	int m = 0;
	for (m = 0; m < x-1; m++)
	{
		k = i + j;
		i = j;
		j = k;
	}
	return k;
}

int main()
{
	int k = 0;
	scanf("%d", &k);
	int sum = fib(k);
	printf("%d", sum);
	return 0;
}

漢諾塔

漢諾塔簡(jiǎn)單了解

輸出一個(gè)數(shù)字的每一位

如輸入 1234 輸出 1 2 3 4

普通解法

這里用取對(duì)數(shù)的方法得到有多少位依次除以位數(shù)的10次方即可

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
void elect(int x)
{
	printf("逆序輸出");
	float k = 0.1;
	int m = 0;
	do
	{
		m = x % 10;
		k = k * 10;
		printf("%d是%f位",m,k);
		x = x / 10;
		if (x < 9)
		{
			k = k * 10;
			printf("%d是%f位", m, k);
			break;
		}
	} while (1);
	printf("\n \n");
}
void elect2(int x)
{
	printf("順序輸出");
	int digit = log10(x) ;
	
	int i = 0;
	int m = 0;
	for (i = pow(10, digit); i >0; i = i / 10)
	{
		m = x / i;
		printf("%d ", m);
		x = x % i;
	}
	
}
int main()
{
	int k = 0;
	scanf("%d", &k);
	//elect(k);
	elect2(k);
	return 0;
}

遞歸解法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void elect(int x)
{ 

	if (x > 9)
	{
		elect(x / 10); //遞歸體 通過(guò)除以10 來(lái)使得問(wèn)題更接近正確答案
		
	}
	printf("%d ", x % 10);//出口

}
int main()
{
	int k = 0;
	scanf("%d", &k);
	elect(k);
	return 0;
}

倒序保存字符串

將參數(shù)字符串中的字符反向排列，不是逆序打印

遞歸解法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdio.h>
#include<string.h>
void reverse_string(char arr[])
{
	int sz = strlen(arr);
	int tmp = *arr;
	*arr = *(arr + sz - 1); //將最后一個(gè)和第一個(gè)互換
	*(arr + sz - 1) = '\0';// 將最后一個(gè)賦值為0
	if (strlen(arr) > 1)//如果不是最后一個(gè)則 指針后移
	{
		reverse_string(arr + 1);
	}
		
	
	*(arr + sz - 1) = tmp;
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%s\n", arr);
}