大家好，今天給各位分享函數(shù)的遞歸調(diào)用例題的一些知識(shí)，其中也會(huì)對(duì)最簡(jiǎn)單的遞歸函數(shù)進(jìn)行解釋，文章篇幅可能偏長(zhǎng)，如果能碰巧解決你現(xiàn)在面臨的問題，別忘了關(guān)注本站，現(xiàn)在就馬上開始吧！

c語(yǔ)言中,一個(gè)函數(shù)可以調(diào)用其他函數(shù),不能調(diào)用自己

錯(cuò)，函數(shù)可以調(diào)用自己，函數(shù)自己調(diào)用自己的這種調(diào)用方式稱為函數(shù)的遞歸調(diào)用,我給你舉個(gè)列子：

intcalc(intnum){

if(num==0){

return0;

}else{

returnnum*calc(num-1);

}

}

這個(gè)函數(shù)就是利用遞歸求任意一個(gè)整數(shù)的階乘

求遞歸算法的時(shí)間復(fù)雜度例題及答案

(1)遞歸執(zhí)行過程

例子：求N!。

這是一個(gè)簡(jiǎn)單的"累乘"問題，用遞歸算法也能解決。

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

0!=1,1!=1n=0,1

因此，遞歸算法如下：

Java代碼

fact(intn){

if(n==0||n==1)

return1;

else

returnn*fact(n-1);

}

以n=3為例，看運(yùn)行過程如下：

fact(3)-----fact(2)-----fact(1)------fact(2)-----fact(3)

------------------------------>------------------------------>

遞歸回溯

遞歸算法在運(yùn)行中不斷調(diào)用自身降低規(guī)模的過程，當(dāng)規(guī)模降為1，即遞歸到fact(1)時(shí)，滿足停止條件停止遞歸，開始回溯(返回調(diào)用算法)并計(jì)算，從fact(1)=1計(jì)算返回到fact(2);計(jì)算2*fact(1)=2返回到fact(3)；計(jì)算3*fact(2)=6，結(jié)束遞歸。

算法的起始模塊也是終止模塊。

(2)遞歸實(shí)現(xiàn)機(jī)制

每一次遞歸調(diào)用，都用一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)"棧"記錄當(dāng)前算法的執(zhí)行狀態(tài)，特別地設(shè)置地址棧，用來(lái)記錄當(dāng)前算法的執(zhí)行位置，以備回溯時(shí)正常返回。遞歸模塊的形式參數(shù)是普通變量，每次遞歸調(diào)用得到的值都是不同的，他們也是由"棧"來(lái)存儲(chǔ)。

(3)遞歸調(diào)用的幾種形式

一般遞歸調(diào)用有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數(shù))。

<1>直接簡(jiǎn)單遞歸調(diào)用：f(n){...a1*f((n-k1)/b1);...};

<2>直接復(fù)雜遞歸調(diào)用：f(n){...a1*f((n-k1)/b1);a2*f((n-k2)/b2);...};

<3>間接遞歸調(diào)用：f(n){...a1*f((n-k1)/b1);...}，

g(n){...a2*f((n-k2)/b2);...}。

2.遞歸算法效率分析方法

遞歸算法的分析方法比較多，最常用的便是迭代法。

迭代法的基本步驟是先將遞歸算法簡(jiǎn)化為對(duì)應(yīng)的遞歸方程，然后通過反復(fù)迭代，將遞歸方程的右端變換成一個(gè)級(jí)數(shù)，最后求級(jí)數(shù)的和，再估計(jì)和的漸進(jìn)階。

<1>例：n!

算法的遞歸方程為：T(n)=T(n-1)+O(1);

迭代展開：T(n)=T(n-1)+O(1)

=T(n-2)+O(1)+O(1)

=T(n-3)+O(1)+O(1)+O(1)

=......

=O(1)+...+O(1)+O(1)+O(1)

=n*O(1)

=O(n)

這個(gè)例子的時(shí)間復(fù)雜性是線性的。

<2>例：如下遞歸方程：

T(n)=2T(n/2)+2,且假設(shè)n=2的k次方。

T(n)=2T(n/2)+2

=2(2T(n/2*2)+2)+2

=4T(n/2*2)+4+2

=4(2T(n/2*2*2)+2)+4+2

=2*2*2T(n/2*2*2)+8+4+2

=...

=2的(k-1)次方*T(n/2的(i-1)次方)+$(i:1~(k-1))2的i次方

=2的(k-1)次方+(2的k次方)-2

=(3/2)*(2的k次方)-2

=(3/2)*n-2

=O(n)

這個(gè)例子的時(shí)間復(fù)雜性也是線性的。

<3>例：如下遞歸方程：

T(n)=2T(n/2)+O(n),且假設(shè)n=2的k次方。

T(n)=2T(n/2)+O(n)

=2T(n/4)+2O(n/2)+O(n)

=...

=O(n)+O(n)+...+O(n)+O(n)+O(n)

=k*O(n)

=O(k*n)

=O(nlog2n)//以2為底

一般地，當(dāng)遞歸方程為T(n)=aT(n/c)+O(n),T(n)的解為：

O(n)(a<c&&c>1)

O(nlog2n)(a=c&&c>1)//以2為底

O(nlogca)(a>c&&c>1)//n的(logca)次方，以c為底

上面介紹的3種遞歸調(diào)用形式，比較常用的是第一種情況，第二種形式也有時(shí)出現(xiàn)，而第三種形式(間接遞歸調(diào)用)使用的較少，且算法分析

比較復(fù)雜。下面舉個(gè)第二種形式的遞歸調(diào)用例子。

<4>遞歸方程為：T(n)=T(n/3)+T(2n/3)+n

為了更好的理解，先畫出遞歸過程相應(yīng)的遞歸樹：

n-------->n

n/32n/3-------->n

n/92n/92n/94n/9-------->n

...............................

--------

總共O(nlogn)

累計(jì)遞歸樹各層的非遞歸項(xiàng)的值，每一層和都等于n，從根到葉的最長(zhǎng)路徑是：

n-->(2/3)n-->(4/9)n-->(12/27)n-->...-->1

設(shè)最長(zhǎng)路徑為k，則應(yīng)該有：

(2/3)的k次方*n=1

得到k=log(2/3)n//以(2/3)為底

于是T(n)<=(K+1)*n=n(log(2/3)n+1)

即T(n)=O(nlogn)

由此例子表明，對(duì)于第二種遞歸形式調(diào)用，借助于遞歸樹，用迭代法進(jìn)行算法分析是簡(jiǎn)單易行的。

c語(yǔ)言，利用遞歸函數(shù)調(diào)用方式，將所輸入的5個(gè)字符，以相反順序打印出來(lái)

#include<stdio.h>voidf(intn){charch;if(n>0){ch=getchar();f(n-1);}elsereturn;printf("%c",ch);}intmain(void){f(5);printf("\n");return0;}

遞歸函數(shù)詳細(xì)講解

（1）邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口。

（2）遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果

在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，進(jìn)入函數(shù)后，首次遞歸調(diào)用自身稱為第1層調(diào)用；從第i層遞歸調(diào)用自身稱為第i+1層。反之，退出第i+1層調(diào)用應(yīng)該返回第i層。

一個(gè)遞歸函數(shù)的調(diào)用過程類似于多個(gè)函數(shù)的嵌套的調(diào)用，只不過調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)工作棧。具體地說，遞歸調(diào)用的內(nèi)部執(zhí)行過程如下：

（1）運(yùn)動(dòng)開始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；

（2）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；

（3）每次遞歸調(diào)用結(jié)束后，將棧頂元

js類中遞歸調(diào)用

你好，這樣是調(diào)用不到的，createA是內(nèi)部函數(shù)，或者說他是A創(chuàng)建的對(duì)象的函數(shù)，應(yīng)該像你test方法使用中那樣調(diào)用。

用C語(yǔ)言，寫一個(gè)函數(shù)用于計(jì)算1！+2！+3！+…+n！的值（使用函數(shù)遞歸完成）

#include<iostream.h>

intfun1(intn)

{

intsum=1;

for(inti=1;i<=n;i++)

sum*=i;

returnsum;

}

intfun(intn)

{

intsum=0;

if(n==1)return1;

elsesum+=fun1(n--);

returnsum;

}

voidmain()

{

intn,sum=0;

cout<<"inputn"<<endl;

cin>>n;

for(inti=1;i<=n;i++)

sum+=fun(i);

cout<<sum<<endl;

}

如果你還想了解更多這方面的信息，記得收藏關(guān)注本站。