腳本之家服務器常用軟件

快捷導航

C語言學好遞歸看這一篇就夠了

更新時間：2021年10月26日 09:16:47 作者：波風張三

遞歸指的是在函數(shù)的定義中使用函數(shù)自身的方法，舉個例子：從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，循環(huán)下去

前言

在一定的時間、空間限制下，人的體力有限，思維力也有限，遞歸思維對實踐最有用的指導，就是把腦力集中于定義問題這個關鍵點上，不用去找解題的過程。定義（問題）即解決（問題），定義即解決！讓大問題變成規(guī)模更小的問題并立即獲得解決，以此作為基礎，讓我們輕松解決函數(shù)本身定義的問題。所以，遞歸在編程中同樣是很重要的一個知識點。

提示：以下是本篇文章正文內容

一、遞歸是什么？

先來看一下定義：

程序調用自身的編程技巧稱為遞歸（ recursion）。

簡單來說，就是在一個函數(shù)里面調用函數(shù)自己本身。

舉個例子：
用遞歸實現(xiàn)求第n個斐波那契數(shù)。

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	//斐波那契數(shù) 1 1 2 3 5 8 13 21 34 51....,除前兩位外，后一個數(shù)的值等于前兩位相加
	int n = 0;
	printf("請輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret=Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

在這里插入圖片描述

所以，我們可以看到，所謂遞歸，其實就是一個函數(shù)里面調用函數(shù)自己本身。具體怎樣調用的，我們下面再講。

二、遞歸的兩個必要條件

1、存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續(xù)。
2、每次遞歸調用之后越來越接近這個限制條件。

分析之后，我們可以得出兩個點

1、結束條件
2、逼近條件

我們在使用遞歸的時候，需要滿足這兩個條件。

總結起來四個字——大事化小

繼續(xù)舉斐波那契數(shù)的例子：

在這里插入圖片描述

三、遞歸是怎樣運行的

我們通過一道題目來講解。

題目：遞歸實現(xiàn)n的k次方
內容：編寫一個函數(shù)實現(xiàn)n的k次方，使用遞歸實現(xiàn)。

【解決思路】
運用遞歸思路，我們只要找到遞歸結束條件和逼近條件。通過分析，我們可以畫出下面這幅圖。

在這里插入圖片描述

【代碼實現(xiàn)】

#include <stdio.h>
double power(int n,int k)
{
	if (k< 0)
	{
		k = -k;
		return 1 / (n*power(n, k - 1));
	}
	else if (k == 0)
		return 1;
	else if (k>0)
	{
		return n * power(n, k - 1);
	}
}
int main()
{
	int n = 0;
	int k = 0;
	printf("請輸入一個整數(shù)：");
	scanf("%d", &n);
	printf("請輸入要求的次方數(shù)：");
	scanf("%d", &k);
	double ret=power(n,k);
	printf("%1f\n", ret);
	return 0;
}

【畫圖詳解遞歸思路】

請?zhí)砑訄D片描述

通過圖解，發(fā)現(xiàn)思路，我們** 存在限制條件k，當滿足這個限制條件的時候，遞歸便不再繼續(xù)。
每次遞歸調用之后越來越接近這個限制條件。**之后輸出的時候就反過來回去。

這個就是遞歸的思路。

四、迭代與遞歸

不知大家有沒有認真思考過上面的求斐波那契數(shù)的代碼，它有什么問題？

在這里插入圖片描述

如果我們這里求的是第50個斐波那契數(shù)呢？大家可以運行一下代碼?？梢园l(fā)現(xiàn)，電腦運行了好久好久才算出結果，費時間。
如果求第10000個斐波那契數(shù)呢？程序就會崩潰。

為什么呢？
我們發(fā)現(xiàn)上面求斐波那契數(shù)的 Fib 函數(shù) 在調用的過程中很多計算其實在一直重復。
因為我們在調用這個函數(shù)的時候，除前兩位外，后一個數(shù)的值等于前兩位相加。這就導致了我們不斷重復計算

如圖：

在這里插入圖片描述

我們可以看到，由于前兩個數(shù)相加等于后一個數(shù)，前兩個數(shù)相加等于后一個數(shù)，所以我們會不斷產生重復的計算。就會造成計算量非常大，效率極低。

那我們如何改進呢？
我們程序存東西的時候，存放在棧區(qū)。
如圖：

在這里插入圖片描述

在調試例子中的Fib函數(shù)的時候，如果你的參數(shù)比較大，那就會報錯： `stack overflow（棧溢出）這樣的信息。
系統(tǒng)分配給程序的?？臻g是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導致一直開辟?？臻g，最終產生?？臻g耗盡的情況，這樣的現(xiàn)象我們稱為棧溢出。

那如何解決上述的問題：

將遞歸改寫成非遞歸。使用static對象替代non-static局部對象。在遞歸函數(shù)設計中，可以使用static對象替代nonstatic局部對象（即棧對象），這不僅可以減少每次遞歸調用和返回時產生和釋放nonstatic對象的開銷，
而且static對象還可以保存遞歸調用的中間狀態(tài)，并且可為各個調用層所訪問。

這里我們介紹迭代。

什么是迭代呢？
【概念】

迭代是重復反饋過程的活動，其目的通常是為了逼近所需目標或結果。每一次對過程的重復稱為一次“迭代”，而每一次迭代得到的結果會作為下一次迭代的初始值。

借用網上的圖片來說明（侵刪）

在這里插入圖片描述

目前對于c語言來說，迭代可以簡單認為是循環(huán)結構。

那么我們如何用迭代的方式求斐波那契數(shù)呢？
【代碼如下】

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;//求出c的值
		a = b;//a賦值給b,也就是a作為b的值
		b = c;//b賦值給c，也就是b作為c的值
		n--;
	}
	return c;
}

int main()
{
	// 1 1 2 3 5 8 13 21 34 55,除前兩位外，后一個數(shù)的值等于前兩位相加
	int n = 0;
	printf("請輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret = Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

在這里插入圖片描述