代碼如下：
public class Test {?
public static void main(String[] args) {?
System.out.println("結果是："+Test.foo(30));?
}?
/**?
?* 常見解法?
?*/?
public static int foo(int i){?
int a=1,b=1;
int c=0;
for(int k=2;k<i;k++){//註意循環次數
c=a+b;
a=b;//註意這句要放在b=c之前
b=c;
}
return c;
}?
}
擴展資料
遞歸思想的內涵：
遞歸就是有去（遞去）有回（歸來）。“有去”是指：遞歸問題必須可以分解為若幹個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就像上面例子中的鑰匙可以打開後面所有門上的鎖壹樣。
“有回”是指 : 這些問題的演化過程是壹個從大到小，由近及遠的過程，並且會有壹個明確的終點(臨界點)，壹旦到達了這個臨界點，就不用再往更小、更遠的地方走下去。最後，從這個臨界點開始，原路返回到原點，原問題解決。
更直接地說，遞歸的基本思想就是把規模大的問題轉化為規模小的相似的子問題來解決。特別地，在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同壹個方法，所以就產生了函數調用它自身的情況，這也正是遞歸的定義所在。
格外重要的是，這個解決問題的函數必須有明確的結束條件，否則就會導致無限遞歸的情況。