文章目錄
- 前言
- 一、遞回是什么？
- 二、 遞回的兩個必要條件
- 三、遞回是怎樣運行的
- 四、迭代與遞回
- 五、遞回與迭代的比較
- 六、 什么時候用遞回
- 最后
前言
在一定的時間、空間限制下，人的體力有限，思維力也有限，遞回思維對實踐最有用的指導，就是把腦力集中于定義問題這個關鍵點上，不用去找解題的程序，定義（問題）即解決（問題），定義即解決！ 讓大問題變成規模更小的問題并立即獲得解決，以此作為基礎，讓我們輕松解決函式本身定義的問題，所以，遞回在編程中同樣是很重要的一個知識點，
提示：以下是本篇文章正文內容
一、遞回是什么？
先來看一下定義：
程式呼叫自身的編程技巧稱為遞回（ recursion），
簡單來說，就是在一個函式里面呼叫函式自己本身，
舉個例子：
用遞回實作求第n個斐波那契數，
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
//斐波那契數 1 1 2 3 5 8 13 21 34 51....,除前兩位外，后一個數的值等于前兩位相加
int n = 0;
printf("請輸入你要查找的斐波那契數：");
scanf("%d", &n);
int ret=Fib(n);
printf("你好，你要需要的值是：%d\n", ret);
return 0;
}
所以，我們可以看到，所謂遞回，其實就是一個函式里面呼叫函式自己本身，具體怎樣呼叫的，我們下面再講，
二、 遞回的兩個必要條件
1、存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
2、 每次遞回呼叫之后越來越接近這個限制條件，
分析之后，我們可以得出兩個點
1、結束條件
2、逼近條件
我們在使用遞回的時候，需要滿足這兩個條件，
總結起來四個字——大事化小
繼續舉斐波那契數的例子：
三、遞回是怎樣運行的
我們通過一道題目來講解，
題目： 遞回實作n的k次方
內容： 撰寫一個函式實作n的k次方，使用遞回實作，
【解決思路】
運用遞回思路，我們只要找到遞回結束條件和逼近條件，通過分析，我們可以畫出下面這幅圖，
【代碼實作】
#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("請輸入一個整數：");
scanf("%d", &n);
printf("請輸入要求的次方數：");
scanf("%d", &k);
double ret=power(n,k);
printf("%1f\n", ret);
return 0;
}
【畫圖詳解遞回思路】
通過圖解，發現思路，我們** 存在限制條件k，當滿足這個限制條件的時候，遞回便不再繼續，
每次遞回呼叫之后越來越接近這個限制條件，**之后輸出的時候就反過來回去，
這個就是遞回的思路，
四、迭代與遞回
不知大家有沒有認真思考過上面的求斐波那契數的代碼，它有什么問題？
如果我們這里求的是第50個斐波那契數呢？大家可以運行一下代碼，可以發現，電腦運行了好久好久才算出結果，費時間，
如果求第10000個斐波那契數呢？程式就會崩潰，
為什么呢？
我們發現上面求斐波那契數的 Fib 函式 在呼叫的程序中很多計算其實在一直重復，
因為我們在呼叫這個函式的時候，除前兩位外，后一個數的值等于前兩位相加，這就導致了我們不斷重復計算
如圖：
我們可以看到，由于前兩個數相加等于后一個數，前兩個數相加等于后一個數，所以我們會不斷產生重復的計算，就會造成計算量非常大，效率極低，
那我們如何改進呢？
我們程式存東西的時候，存放在堆疊區，
如圖：
在除錯 例子中的Fib函式的時候，如果你的引數比較大，那就會報錯： `stack overflow（堆疊溢位） 這樣的資訊，
系統分配給程式的堆疊空間是有限的，但是如果出現了死回圈，或者（死遞回），這樣有可能導致一直開辟堆疊空間，最終產生堆疊空間耗盡的情況，這樣的現象我們稱為堆疊溢位，
那如何解決上述的問題：
- 將遞回改寫成非遞回，
- 使用static物件替代non-static區域物件，在遞回函式設計中，可以使用static物件替代nonstatic局 部物件（即堆疊物件），這不僅可以減少每次遞回呼叫和回傳時產生和釋放nonstatic物件的開銷，
而且static物件還可以保存遞回呼叫的中間狀態，并且可為各個呼叫層所訪問，
這里我們介紹迭代，
什么是迭代呢？
【概念】
迭代是重復反饋程序的活動，其目的通常是為了逼近所需目標或結果，每一次對程序的重復稱為一次“迭代”，而每一次迭代得到的結果會作為下一次迭代的初始值，
借用網上的圖片來說明（侵刪）
目前對于c語言來說，迭代可以簡單認為是回圈結構，
那么我們如何用迭代的方式求斐波那契數呢？
【代碼如下】
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,除前兩位外，后一個數的值等于前兩位相加
int n = 0;
printf("請輸入你要查找的斐波那契數：");
scanf("%d", &n);
int ret = Fib(n);
printf("你好，你要需要的值是：%d\n", ret);
return 0;
}
這樣，我們算很大的數都能一下子算出來了，雖然不能保證正確，因為堆疊溢位了，但是效率很快，
五、遞回與迭代的比較
我們用一個表格來分析：
【注意】
- 許多問題是以遞回的形式進行解釋的，這只是因為它比非遞回的形式更為清晰，
- 但是這些問題的迭代實作往往比遞回實作效率更高，雖然代碼的可讀性稍微差些，
- 當一個問題相當復雜，難以用迭代實作時，此時遞回實作的簡潔性便可以補償它所帶來的運行時開銷，
六、 什么時候用遞回
什么時候用遞回呢？
（1）當解決一個問題時，遞回和非遞回都可以使用，且沒有明顯問題，那就可以使用遞回
（2）當解決一個問題時，遞回寫起來很簡單，非遞回比較復雜，且遞回沒有明顯問題，那就用遞回
（3）如果說，用遞回解決問題，寫起來簡單，但是有明顯問題，那就不能使用遞回
最后
以上內容是通過本人學習的理解和網上資料的整理梳理出來的遞回與迭代的一些內容，有錯漏之處，還請各位多多包涵與指出，共同進步，共同成長!
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298951.html
標籤：其他