遞歸調用
一種特殊嵌套調用
遞歸調用是一種特殊的嵌套調用，是某個函數調用自己或者是調用其他函數后再次調用自己的，只要函數之間互相調用能產生循環的則一定是遞歸調用，遞歸調用一種解決方案，一種是邏輯思想，將一個大工作分為逐漸減小的小工作，比如說一個和尚要搬50塊石頭，他想，只要先搬走49塊，那剩下的一塊就能搬完了，然後考慮那49塊，只要先搬走48塊，那剩下的一塊就能搬完了，遞歸是一種思想，只不過在程序中，就是依靠函數嵌套這個特性來實現了。
遞歸調用
fun(形參){
fun(參數值1)//第一次遞歸調用
fun(參數值2)//第二次遞歸調用
C語言中的遞歸
計算階乘的代碼
long fact(long n)
{
if(n==0||n==1)return 1L;
else return n*fact(n-1);
}
這個函數叫做fact，它自己調用自己，這個就是一個典型的遞歸調用，調用過程類似一個棧。
注: 主調函數又是被調函數。執行遞歸函數將反覆調用其自身。每調用一次就進入新的一層。
int f (int x)
{
int y;
z=f(y);
return z;
}這個函數是一個遞歸函數。但是運行該函數將無休止地調用其自身，這當然是不正確的。為了防止遞歸調用無終止地進行，必須在函數內有終止遞歸調用的手段。常用的辦法是加條件判斷，滿足某種條件后就不再作遞歸調用，然後逐層返回。下面舉例說明遞歸調用的執行過程。
註：鏈表在某種程度上就是遞歸的調用.
Pascal中的遞歸
const
z=10000;
var
a:array[0..z+1]of integer;
n,j,i,k:longint;
begin
readln(n);write(n,'!=');
begin
a[1]:=1;
for i:=1 to n do
begin
for j:=1 to z do
a[j]:=a[j]*i;
for k:=1 to z do
begin
a[k+1]:=a[k+1]+a[k]div 10;
a[k]:=a[k]mod 10;
end;
end;
i:=z;k:=0;
repeat
if a[i]<>0 then k:=1;
i:=i-1;
until k=1;
k:=0;
for j:=i+1 downto 1 do
write(a[j]);
end;
writeln;
end.
c++語言中的遞歸
#include
using namespace std;
int fac(int n)
{
int s=1;
for (int i=n;i>0;i--)
{
if (s<=s*i) s=s*i;
else
{
cout<<"over int area"<
return 0;
};
}
return s;
}
void main()
JAVA寫的遞歸調用
public class TestDg{
public static void main(String[] args){
System.out.println(method(5));
}
public static int method(int n){
if (n==1)
return 1;
else
return n * method(n - 1);
}
}
漢諾塔------軟體遞歸調用裡面最經典的一個案例
#include
int c=0;
void move(char x,int n,char z)
{
printf("第%i步：將%i號盤從%c移到%c\n",++c,n,x,z);
}
void hanoi(int n,char x,char y,char z)
{
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
void main()
{
int n;
printf("3個塔座為a、b、c，圓盤最初在a座，藉助b座移到c座。請輸入圓盤數：");
scanf("%d",&n);
hanoi(n,'a','b','c');
}
一個函數的運行期間調用另一個函數時，在運行被調用函數之前，系統需要完成3件事情：
（1）將所有的實參、返回地址等信息傳遞給被調用函數保存；
（2）為被調用函數的局部變數分配存儲區；
（3）將控制轉移到被調函數的入口。
而從被調用函數返回調用函數之前，系統也應完成3件工作：
（1）保存被調函數的計算結果；
（2）釋放被調函數的數據區；
（3）依照被調函數保存的返回地址將控制轉移到調用函數。當有多個函數構成嵌套調用時，按照后調用先返回的原則。
所有遞歸函數的結構都是類似的。
（1）函數要直接或間接調用自身。
（2）要有遞歸終止條件檢查，即遞歸終止的條件被滿足后，則不再調用自身函數。
（3）如果不滿足遞歸終止的條件，則調用涉及遞歸調用的表達式。在調用函數自身時，有關終止條件的參數要發生變化，而且需向遞歸終止的方向變化。
函數的調用原則和數據結構棧的實現是相一致。也說明函數調用是通過棧實現的。
基本信息
- 中文名
- 遞歸調用
- 外文名
- recursive invocation
- 遞歸舉例
- 計算階乘的代碼
- 函數模型
- fun（形參）
目錄