遞迴函式是什麼意思，遞迴的定義是什麼

許多初學者往往對遞迴感到困惑，並花費大量時間在遞迴上。 其實教科書上的例子很經典，但說的有點嘮叨。 初學者會看大頭。

程式設計是解決問題的，實際上許多問題相對簡單，沒有河內塔那麼複雜。 我們不必問遞迴是如何實現的，我們只需要能夠使用遞迴，我們可以用遞迴為我們解決一些問題，僅此而已。

讓我們從乙個例子開始：

有乙個費波那契數列：

問題是：找到這個序列中的第 n 個數字。

由於它的函式原型是：f（n）=f（n-1）+f（n-2），可以用遞迴輕鬆寫出來，一點也不麻煩：

int febc(int n)

很簡單，沒什麼好說的。 但是你能寫出相應的遞迴函式嗎？

如果你說得太多，你不知道它是什麼。

問：最好不要複製貼上...

遞迴是呼叫本身出現在函式中的現象，如最簡單的示例，求階乘：

當 n=0 或 1 時，n！ =1；當 n>1， n！ =n*(n-1)!通過這樣的想法，程式被寫成：

int fun(int n)

if(n<2)

return 1;

elsereturn n*fun(n-1);

看到fun函式自稱fun，可想而知，可以一步一步得到計算結果。

樓上的兩人怎麼還要說得這麼複雜！

遞迴函式是呼叫自身的函式（僅在呼叫時具有不同的引數）。

遞迴是指由函式、過程或子程式在正在執行的程式中直接或間接呼叫自身引起的重入現象。

在計算機程式設計中，遞迴是指函式不斷引用自身直到已知引用物件的過程。

使用遞迴來解決問題，清晰地思考，少。 但是，在主流高階語言中（使用遞迴演算法會占用更多的堆疊空間，因此在堆疊大小有限時應避免使用。 所有遞迴演算法都可以重寫為非遞迴等效演算法。

呼叫自己的程式設計技術的程式稱為遞迴。 遞迴在程式語言中被廣泛用作一種演算法。

乙個過程或函式在其定義或描述中有乙個直接或間接呼叫自身的方法，它通常將乙個大而複雜的問題轉化為乙個類似於原始問題的小問題來解決，而遞迴策略只需要少量的程式來描述求解過程中所需的多次重複計算， 這大大減少了程式的數量。

遞迴的力量在於在有限語句中定義無限的物件集。 通常，遞迴需要邊界條件、遞迴前向段和遞迴返回段。 當邊界條件不滿足時，遞迴推進; 當滿足邊界條件時，將返回回滾。

遞迴的缺點：蘆葦核

遞迴演算法與普通迴圈等常用演算法相比解決了這個問題，執行效率低。 因此，應避免遞迴，除非沒有更好的演算法或在遞迴更合適的特定情況下。 在遞迴呼叫過程中，系統為每一層的返回點、本地數量等開啟乙個堆疊來儲存。

過多的遞迴很容易導致堆疊溢位等。

以上內容參考：百科全書 - 遞迴。

遞迴和迭代都是迴圈的型別。

簡單地說，遞迴就是函式本身的重複呼叫來實現迴圈。 迭代與普通迴圈的區別在於，在迴圈中參與操作的變數也是儲存結果的變數，當前儲存的結果作為下乙個迴圈計算的初始值。

在遞迴迴圈中，當滿足終止條件時，它會逐層返回到末尾。 迭代使用計數器來結束迴圈。 當然，在許多情況下，它是一種多迴圈混合物，具體取決於具體需求。

遞迴的乙個例子是，給定乙個整數陣列，使用減半查詢返回陣列中指定值的索引，假設陣列是排序的，並且為了描述，假設元素都是正數，陣列的長度是 2 的整數倍。

半拆分查詢是一種查詢型別，比遍歷所有元素要快得多。

int find(int *ary,int index,int len,int value)

if（len==1） 最後乙個元素。

if (ary[index]==value)return index;成功的查詢將返回乙個索引。

return -1;失敗，返回 -1

如果長度大於 1，則執行半倍遞迴查詢。

int half=len/2;

檢查選中的值是否大於上半部分的最後乙個值，如果大於，則遞迴查詢後半部分。

if(value>ary[index+half-1])

return find(ary,index+half,half,value);

否則，以遞迴方式查詢上半部分。

return find(ary,index,half,value);

迭代的經典例子是實數的累加，例如從 1 到 100 的所有實數之和。

int v=1;

for(i=2;i<=100;i++)

v=v+i;

1.主要方法求解遞迴公式。

求解大多數遞迴表示式的公式。 給出遞迴公式：t（n） =a * t（n b） +f（n），其中 a>=1， b>1， f（n） 是給定函式，t（n） 是在非負整數上定義的遞迴表示式。

2.遞迴樹求解。

我們可以使用遞迴樹來猜測解的上限，然後使用替換方法來證明解的正確性。 求解遞迴樹的準確性取決於繪製遞迴樹的精度。

3.替代方法。

例如，如果我們求解遞迴 t（n） = 2t（n 2） + n，我們猜測解是 o（nlgn），並且我們發現乙個常數 c，使得 t（n）<=cnlgn。

即，t（n） <2c（n 2）lg（n 2）+n <=cnlgn-cnlg2+n = cnlgn-cn+n

只要 c>=1 和 t（n）<=cnlgn，我們的猜測就是正確的。

需要注意的是，替換方法完全是經驗性的，通常上限由遞迴樹確定，然後用替換方法進行證明。