java遞歸筆試題是常見的java筆試題，動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編就為大家整理一些，希望對(duì)大家能夠有所幫助。

1、請(qǐng)寫一段代碼來(lái)計(jì)算給定文本內(nèi)字符“A”的個(gè)數(shù)。分別用迭代和遞歸兩種方式。

假設(shè)給定文本為”AAA rating”。迭代方式就很直觀，如下：

public?class?Iteration?{
????public?int?countA(String?input)?{
????????if?(input?==?null?||?input.length(?)?==?0)?{
????????????return?0;
????????}
????????int?count?=?0;
????????for?(int?i?=?0;?i?<?input.length(?);?i++)?{
????????????if(input.substring(i,?i+1).equals("A")){
????????????????count++;
????????????}
????????}
????????return?count;
????}
????public?static?void?main(String[?]?args)?{
??????????System.out.println(new?Iteration(?).countA("AAA?rating"));?????//?Ans.3
????}
}

接下來(lái)，遞歸方式的代碼如下：

public?class?RecursiveCall?{
????public?int?countA(String?input)?{
????????//?exit?condition?–?recursive?calls?must?have?an?exit?condition
????????if?(input?==?null?||?input.length(?)?==?0)?{
????????????return?0;
????????}
?
????????int?count?=?0;
?
????????//check?first?character?of?the?input
????????if?(input.substring(0,?1).equals("A"))?{
????????????count?=?1;
????????}
?
????????//recursive?call?to?evaluate?rest?of?the?input
????????//(i.e.??2nd?character?onwards)
????????return?count?+?countA(input.substring(1));
????}
?
????public?static?void?main(String[?]?args)?{
????????System.out.println(new?RecursiveCall(?).countA("AAA?rating"));??//?Ans.?3
????}
}

遞歸比較難以理解，我們用下面的圖來(lái)進(jìn)行說(shuō)明。

2、理解遞歸需要了解哪些概念?

java面試題可重入方法(re-entrant method)是可以安全進(jìn)入的方法，即使同一個(gè)方法正在被執(zhí)行，深入到同一個(gè)線程的調(diào)用棧里面也不會(huì)影響此次執(zhí)行的安全性。一個(gè)非可重入方法則不是可以安全進(jìn)入的。例如，加入寫文件或者向文件中寫入日志的方法不是可重入方法時(shí)，有可能會(huì)毀壞那個(gè)文件。

如果一個(gè)方法調(diào)用了其自身的話，我們稱之為遞歸調(diào)用。假定棧空間足夠的話，盡管遞歸調(diào)用比較難以調(diào)試，在Java語(yǔ)言中實(shí)現(xiàn)遞歸調(diào)用也是完全可行的。遞歸方法是眾多算法中替代循環(huán)的一個(gè)不錯(cuò)選擇。所有的遞歸方法都是可重入的，但是不是所有可重入的方法都是遞歸的。

棧遵守LIFO(Last In First Out)規(guī)則，因此遞歸調(diào)用方法能夠記住“調(diào)用者”并且知道此輪執(zhí)行結(jié)束之返回至當(dāng)初的被調(diào)用位置。遞歸利用系統(tǒng)棧來(lái)存儲(chǔ)方法調(diào)用的返回地址。 Java是一種基于棧設(shè)計(jì)的編程語(yǔ)言。

3、什么情況下應(yīng)該采用遞歸?

上面的例子中其實(shí)不必采用遞歸，循環(huán)的方式可以達(dá)到目的，但是在某些情況下采用遞歸方式則代碼會(huì)更加簡(jiǎn)短易讀。遞歸方法在循環(huán)樹結(jié)構(gòu)以及避免丑陋的嵌套循環(huán)的情況下是非常好用的。

4、什么是尾遞歸，為什么需要尾遞歸?上面的代碼用尾遞歸方式如何重寫?

常規(guī)遞歸方法(亦稱，頭遞歸)在上面演示了，這種方式會(huì)增加調(diào)用棧的大小。每次遞歸，其入口需要被記錄在棧中。方法返回之前需要給countA(input.substring(1)的結(jié)果加一個(gè)count。假定count大于1，那么返回結(jié)果就是count + countA(input.substring(1))，當(dāng)然事先要算出來(lái)countA(input.substring(1))才行。同時(shí)，這也意味著直到countA(input.substring(1)計(jì)算出來(lái)才能得到最終的結(jié)果。因此，最后需要做的事其實(shí)是加法運(yùn)算，而非遞歸本身。

尾遞歸的好處是什么?

java面試題在尾遞歸中，最后要做的是遞歸，加法運(yùn)算在之前就已經(jīng)完成了。一輪遞歸調(diào)用完畢后就沒(méi)有其他事情了(除了加法運(yùn)算)，因此調(diào)用時(shí)生成的信息也就沒(méi)什么用了。這些無(wú)用信息可以丟棄，然后用一組新的參數(shù)來(lái)調(diào)用一次遞歸方法來(lái)產(chǎn)生一個(gè)新的結(jié)果。這也就是說(shuō)，棧調(diào)用減少帶來(lái)了內(nèi)存消耗減少并且程序的性能更好。

尾遞歸重寫的代碼如下:

public?class?TailRecursiveCall?{
?public?int?countA(String?input)?{
?
??//?exit?condition?–?recursive?calls?must?have?an?exit?condition
??if?(input?==?null?||?input.length()?==?0)?{
???return?0;
??}
?
??return?countA(input,?0)?;
?}
?
?public?int?countA(String?input,?int?count)?{
??if?(input.length()?==?0)?{
???return?count;
??}
?
??//?check?first?character?of?the?input
??if?(input.substring(0,?1).equals("A"))?{
???count?=?count?+?1;
??}
?
??//?recursive?call?is?the?last?call?as?the?count?is?cumulative
??return?countA(input.substring(1),?count);
?}
?
?public?static?void?main(String[]?args)?{
??System.out.println(new?TailRecursiveCall().countA("AAA?rating"));
?}
}

以上就是動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“java遞歸筆試題參考”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。