快捷導(dǎo)航

c語言深入理解函數(shù)的遞歸

更新時間：2022年02月09日 15:13:55 作者：誠摯的喬治

這一章講解的是函數(shù)的遞歸，因?yàn)檫f歸函數(shù)是一個非常重要求解復(fù)雜問題的方法之一，在學(xué)習(xí)算法的過程之中我們也會遇到他，所以我想對它進(jìn)行一次講解，希望能幫助其他人，也能幫助我自己來梳理一遍。下面我會通過一些題目的講解去認(rèn)識遞歸函數(shù)

前言：

?首先，遞歸是什么，遞歸就是在定義函數(shù)時，然后在函數(shù)里調(diào)用這個函數(shù)，通俗講，就是函數(shù)自己調(diào)用自己。那么遞歸的好處是什么呢？它能夠?qū)?fù)雜的問題，用少量的代碼來表示，增加了代碼的可讀性。

但是遞歸有一個條件，就是每一次的重復(fù)調(diào)用都需要越接近這個限制條件。

1.用遞歸打印一個整數(shù)的每一位

題目的要求是打印一個整數(shù)的每一位，就比如說1234，打印的結(jié)果就是1234，我們學(xué)過用循環(huán)打印過4321，但順著打印，用循環(huán)來做，相對于遞歸來解，就會有點(diǎn)復(fù)雜。

#include<stdio.h>//打印一個整數(shù)的每一位,用遞歸
print(int n)
{
	int i = 0;
	if(n>9)
	{
		print(n / 10);
	}
	printf("%d", n%10);
}
int main()
{
	int num = 0;
	printf("請輸入一個整數(shù)：");
	scanf("%d",&num);
	print(num);
	return 0;
}

這道題就是利用了遞歸的思想，此時的遞歸函數(shù)就是print函數(shù)。

首先是遞歸中的“遞”

當(dāng)我們在scanf函數(shù)中輸入一個整數(shù)1234時，第一次進(jìn)入print函數(shù)里，通過if語句再次進(jìn)入print函數(shù)里，注意這時還未進(jìn)行printf打印出結(jié)果。

這就到了第二次進(jìn)入print函數(shù)里，此時進(jìn)入函數(shù)的數(shù)子不在時?1234，而是除以十后的123，進(jìn)入print函數(shù)后，再次通過if語句，進(jìn)入print函數(shù)，注意這時也還未進(jìn)行printf打印出結(jié)果。

第三次進(jìn)入print函數(shù)里，是除以十后的12，12依然大于9，所以再次通過if語句，進(jìn)入print函數(shù)，這時進(jìn)入print函數(shù)的是除以十后的1.注意這時也還未進(jìn)行printf打印出結(jié)果

第四次調(diào)用print函數(shù)時，此時的n就是1，顯然不滿足大于9的條件。這時的1余以十的結(jié)果還是1，于是首先打印出1。

然后就是遞歸中的“歸”

打印完1后，第四次進(jìn)入循環(huán)的過程就結(jié)束了，此時，接著歸回上一次的循環(huán)，我們知道上次的循環(huán)到進(jìn)入if語句后，就沒有再次往下進(jìn)行，歸時就接著上次的操作，往下進(jìn)行運(yùn)行，就打印12余十的結(jié)果2，同理，就打印出最終的1234.

2.遞歸求n的階乘

你是否還記得上次求n的階乘還是說在上次。這次用遞歸來求解n的階乘，實(shí)際上也是非常的簡單，先寫出不用遞歸來求n的循環(huán)。

#include<stdio.h>//求n的階乘
int main()
{
	int num = 0; int i = 0; int ret = 1;
	printf("請輸入一個值：");
	scanf("%d",&num);
	for (i = 2; i <=num; i++)
	{
		ret *= i;
	}
	printf("%d", ret);
	return 0;
}

然后就是遞歸求n的階乘：

#include<stdio.h>//求n的階乘
int fac(int n)
{
	if (n > 1)
		return n * fac(n - 1);
	else
		return 1;
}
int main()
{
	int ret = 0;
	int num = 0;
	printf("請輸入n的值：");
	scanf("%d", &num);
	ret=fac(num);
	printf("%d", ret);
	return 0;
}

這時的n就是輸入的值，fac（n-1）就重復(fù)調(diào)用此函數(shù)，又可以無限接近這個n大于1的這個條件。這就用到了遞歸的思想。我們知道求n的階乘，也可以表示成n乘以（n-1）的階乘。以此重復(fù)，n-1等于1時就停止。就達(dá)到求n的階乘的目的~~

3.用遞歸和非遞歸求字符串的長度

求字符串的長度，不就是strlen函數(shù)嗎？

但是，不用這個庫函數(shù)呢

我們依然可以用兩種方法進(jìn)行求解。

首先用非遞歸來求字符串的長度，也就是用我們自己的my_strlen函數(shù)。

#include<stdio.h>//用非遞歸求字符串的長度
my_strlen(char *arr)
{
	int a = 0; int ret = 0;
	char c = *(arr+a);
	while(arr[a] != '\0')
	{
		a++;
		ret++;
		}
	return ret;
}
int main()
{
	int ret = 0;
	char arr[] = "abc";
	ret=my_strlen(arr);
 	printf("%d", ret);
	return 0;
}

遞歸如下：

#include<stdio.h>
my_strlen(char* arr)
{
	int i = 0;
	if (*arr == '\0')
		return 0;
	if (*arr != '\0')
		return 1 + my_strlen(arr + 1);
}
int main()
{
	int ret = 0;
	char arr[] = "abc";
	ret = my_strlen(arr);
	printf("%d", ret);
	return 0;
}

這道題的思路就是一個一個字符來數(shù)，知道\0來結(jié)束此程序，我們知道“abc”是由abc\0四個字符組成，而遞歸的思路就是先數(shù)出a這個字符然后再數(shù)b，直到\0結(jié)束。

4.輸入一個數(shù)求各位數(shù)之和

這題的意思就是求出一個整數(shù)個十百千位之和，比如1234結(jié)果為10；

#include<stdio.h>//輸入一個數(shù)求各位數(shù)之和
sum(int x)
{
	int ret = 0;
	if (x > 9)
	{
		return  x % 10 + sum(x / 10);
	}
	else
		return x;
}
int main()
{
	int num = 0;
	printf("請輸入一個數(shù)之和：");
	scanf("%d", &num);
	printf("%d",sum(num));
	return 0;
}

5.用遞歸求n的k次方

#include<stdio.h>//用遞歸求n的k次方
tmp(int x,int y)
{
	if (y <= 0)
	{
		return 1;
	}
	else
		return x * tmp(x, y - 1);
}
int main()
{
	int k = 0; int n = 0;
	printf("請輸入一個n和k：");
	scanf("%d %d",&n, &k);
	int ret=tmp(n,k);
	printf("%d", ret);
	return 0;
}

6.計算斐波那契數(shù)

#include<stdio.h>//計算斐波那契數(shù)
feibona(int n)
{
	
	if (n >= 3)
		return feibona(n - 1) + feibona(n - 2);
	else 1;
}
int main()
{
	int n = 0;
	printf("請輸入一個n：");
	scanf("%d", &n);
	int ret=feibona(n);
	printf("%d", ret);
	return 0;
}

斐波那契數(shù)就是1 1 2 3 5 8 13……前兩個數(shù)之和得到第三個數(shù)

這里給出不用遞歸的求解：

#include<stdio.h>//用非遞歸求斐波那契數(shù)\
int feibona(int N)
{
int i = 1;
int j = 1;
int sum = i + j;
for (i = 4; i <= N; i++)
{
	i = j;
	j = sum;
	sum = i + j;
}
return sum;
}
int main()
{
	printf("請輸入一個n：");
	scanf("%d",&n);
	int ret=feibona(n);
	printf("%d", ret);
	return 0;
}

結(jié)語：

以上這些都利用到了遞歸函數(shù)的求解方法，思想都是差不多的，如果你仔細(xì)琢磨，會發(fā)現(xiàn)遞歸的魅力，這些例題可以拿來復(fù)習(xí)，歡迎大家支持點(diǎn)贊收藏~~

到此這篇關(guān)于c語言深入理解函數(shù)的遞歸的文章就介紹到這了,更多相關(guān)c語言函數(shù)遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: