快捷導航

C語言之函數(shù)遞歸的實現(xiàn)

更新時間：2023年07月05日 08:51:19 作者：iLoyo_

本文主要介紹了C語言之函數(shù)遞歸的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

1. 概念

C語言中，函數(shù)直接或間接調(diào)用函數(shù)本身，則該函數(shù)稱為遞歸函數(shù)。

遞歸做為一種算法在程序設(shè)計語言中廣泛應用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。

遞歸的主要思考方式在于：把大事化小

2. 遞歸的兩個必要條件

//例子：
void func()
{
	//...
	if(...)
		func();//調(diào)用自身
	else
	//...
}

在上面的例子中能夠看出，它必須滿足以下兩個條件：

?? 在每一次調(diào)用自己時，必須是（在某種意義上）更接近于解；?? 必須有一個終止處理或計算的限制條件，當滿足這個限制條件的時候，遞歸便不再繼續(xù)。

??實例1：

接收一個整型值（無符號），按照順序打印他的每一位。
例如：
　　　輸入123，輸出1 2 3

非遞歸：

#include<stdio.h>
int main()
{
	int n=123;
	int a = n / 100;//取百位
	int b = (n / 10)%10;//取十位
	int c = n % 10;//取個位
	//依次輸出
	printf("%d %d %d\n", a, b, c);
	return 0;
}

遞歸：

#include<stdio.h>
void Fun_c(int x)
{
	if (x >9)//限制條件
	{
	Fun_c(x/10);
	}
	printf("%d ", x%10);
}
int main()
{
	int n;
	scanf("%d", &n);
	Fun_c(n);
	return 0;
}

圖解：

??實例2：

編寫函數(shù)不允許創(chuàng)建臨時變量，求字符串的長度。

int Length(char* s)
{
	if (*s == '\0')//限制條件
		return 0;
	else
		return 1 + Length(s + 1);
}
#include<stdio.h>
int main()
{
	char* ch = "iloveC";//字符串結(jié)束標志:'\0'
	int len = Length(ch);
	printf("%d", len);
	return 0;
}

第一次 s=“iloveC\0”------5+1
第二次 s=“loveC\0”-----4+1
第三次 s=“oveC\0”----3+1
第四次 s=“veC\0”----2+1 ( 回退)
第五次 s=“eC\0”----1+1
第六次 s=“C\0”----1+0
第七次 s=“\0”-----0

3. 遞歸與迭代

3.1 求n的階乘

//遞歸
#include<stdio.h>
int Fac(int n)
{
	if (n == 1)//限制條件
		return 1;
	else
		return n * Fac(n - 1);
}
int main()
{
	int n;
	scanf("%d", &n);
	int temp = Fac(n);
	printf("%d\n", temp);
	return 0;
}

//迭代
int Fac(int n)
{
	int temp = 1;
	for (int i = 1; i <= n; i++)
	{
		temp = temp * i;
	}
	return temp;
}
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", Fac(n));
	return 0;
}

3.2 求第n個斐波那契數(shù)

1 1 2 3 5 8 13 21…
從第三位開始，后一項等于前兩項之和

//遞歸
#include<stdio.h>
int Fib(int n)
{
	if (n == 1 || n == 2)//限制條件
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", Fib(n));
	return 0;
}

//迭代
#include<stdio.h>
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", Fib(n));
	return 0;
}

注：
?? 許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸的形式更為清晰。
?? 但是這些問題的迭代實現(xiàn)往往比遞歸實現(xiàn)效率更高，雖然代碼的可讀性稍微差些。
?? 當一個問題相當復雜，難以用迭代實現(xiàn)時，此時遞歸實現(xiàn)的簡潔性便可以補償它所帶來的運行時開銷。