java遞歸筆試題參考

java遞歸筆試題是常見(jiàn)的java筆試題，天津卓眾教育java培訓(xùn)機(jī)構(gòu)的小編就為大家整理一些，希望對(duì)大家能夠有所幫助。

1、請(qǐng)寫(xiě)一段代碼來(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)入的。例如，加入寫(xiě)文件或者向文件中寫(xiě)入日志的方法不是可重入方法時(shí)，有可能會(huì)毀壞那個(gè)文件。

如果一個(gè)方法調(diào)用了其自身的話，我們稱之為遞歸調(diào)用。假定?？臻g足夠的話，盡管遞歸調(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)樹(shù)結(jié)構(gòu)以及避免丑陋的嵌套循環(huán)的情況下是非常好用的。

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

常規(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)存消耗減少并且程序的性能更好。

尾遞歸重寫(xiě)的代碼如下:

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"));?}}

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