誰來幫我解釋遞迴函式

這是關於在你編寫函式之前假裝函式已經寫好了。

遞迴有兩個過程：回溯和迭代。

例如：find n！：

n!=n*(n-1)!

n-1)!=n*(n-1)*(n-2)!

要求出去！ ，並要求 （n-1）！，依此類推... 直到 1！ =1，這是回溯過程。

n!=(n-1)!*n;這是乙個迭代過程......

這是為了迴圈自己。

迴圈在某個階段退出......

以譚浩強為例：

int s(int a)

int b;

if(a<0) printf("ok");

else if(a==1)b=1;

else b=s(a-1)+a;

return b ;

main()

int c,h;

scanf("%d",&c);

h=s(c);

printf("%d",h);

設 c=3;s=呼叫 s 函式，如果 3 小於 0，則輸出 OK; 否則，則判斷a是否等於1，其中a為3且3不等於1，則b=s（3-1）+3;也就是說，稱呼自己，然後從頭開始，但是此時a已經是2了，判斷2是小於0還是等於1，顯然2不小於0也不等於1，那麼就稱自己為b=s（2-1）+2，此時a是1,1不小於0， 但是 1 等於 1，這裡，是時候逐層返回了，將 b = 1 返回到 b = s （2-1） + 2。在本例中，s（2-1）=1（括號中不是 2-1=1）是由 s 函式呼叫計算和返回的值。

然後是：b=s（2-1）+2 的結果返回為 b=s（3-1）+3，b=s（2-1）+2 返回 3 的值，則 s（3-1）=3。

如果 a=3，經過遞迴函式計算，最終結果是：b=5 呢？ 你明白嗎？ 你不明白就別問我，我只有這個層次，再深一點，我和你一樣。

純粹的肉搏戰，要拿點。

這很簡單，稱自己為堆疊中的壓力堆疊。

如果你不了解堆疊，你就不了解遞迴。

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，我們的猜測就是正確的。

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

遞迴函式的基本思想如下：

遞迴是玩棚子的方法，自稱遞迴功能：有乙個臨界點 當乙個方法被執行時，或者當它遇到 rerun 時，它會返回，並且函式不在堆疊中。

要解決的問題的解是輸入變數 x 的函式 f（x），並通過找到函式 g（ ） 使得 f（x） = g（f（x-1））。

現在 f（0） 的值是已知的，f（x） 的值可以通過 f（0） 和 g（ ） 找到。

擴充套件到多個輸入變數x、y、z等，x-1也可以推廣到x-x1，只要是遞迴地朝“退出”的方向。

將乙個問題劃分為一組子問題，這些子問題依次解決。

子問題是水平的、同質遞迴的：乙個問題逐漸分解為子問題。

子問題和原始問題之間存在縱向的、同質的關係。

語法上：函式在執行時呼叫自身。

直接呼叫：直接在 fun（） 中執行 fun（）。

間接呼叫：在 fun1（） 中執行 fun2（）; 在 fun2（） 中，fun1（） 也被執行以區分遞迴和列舉。

遞迴的三個要點：

遞迴：如何將原始問題劃分為子問題。

遞迴退出：遞迴終止條件，即最小子問題的解，可以允許多個退出。

邊界函式：改變核問題大小的函式，保證遞迴的尺度接近退出條件，得到階乘的遞迴過程。

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

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

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

遞迴的乙個例子是，給定乙個整數陣列，使用減半查詢返回陣列中指定值的索引，假設陣列是排序的，並且為了描述，假設元素都是正數，陣列的長度是 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;

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

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

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