1 遞歸簡論

需求：求出f(x)=2f(x-1)+x2的值。滿足f(0)=0

public class Recursion {// 需求： 求出f(x)=2f(x-1)+x2的值。滿足f(0)=0public static void main(String[] args) {int f = f(1);System.out.println(f);}public static int f(int x){// 1 當x=1的時候f(1)=1 f(0)=0 f(2)=2f(1)+4=6if(x==0)return x;return 2*f(x-1)+x*x;} }

像上面的情況來說。我們知道f(0)=0;如果不知道這個情況，那么程序?qū)⒉粫嬎愠鰜怼＿@種情況稱之為基準情況，也就是說不需要經(jīng)過遞歸而直接就可以計算出來。這就是基準情況。?
接著我們再來看一個情況：如下代碼所示。

public static int bad(int n){if(n==0)return 0;return bad(n/3+1)+n-1; } Exception in thread “main” java.lang.StackOverflowError at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25) at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25) at com.gosaint.firstChapter.Introduction.Recursion.bad(Recursion.java:25)

程序出現(xiàn)了棧溢出。這是因為沒有基準情況的。當n=1,此時bad(1)。但是bad(1)的值不知道，因此無法繼續(xù)遞歸下去。也就是說，遞歸必須要滿足的條件:?
a 必須存在基準情況?
b 能夠持續(xù)不斷的進行單方向的循環(huán)

需求：計算 一個數(shù)N中的二進制中1的個數(shù)：?
計算說明：?
1 對于一個數(shù)，首先將其轉(zhuǎn)換為二進制，對于其中1或者0的個數(shù)分別可以如下的計算：?
n&(n-1):其中計算1的個數(shù)?
n|(n+1):其中計算出0的個數(shù)?
詳細的解釋下：如9的二進制是：1001。其中的1的個數(shù)為2。9&8的結(jié)果是1000。消除了右邊的1。繼續(xù)循環(huán)消除。從而得到1的個數(shù)。?
2 對于一個奇數(shù)而言，其中二進制中1的個數(shù)為n/2的數(shù)中二進制的個數(shù)加1?
遞歸的方式計算一個數(shù)中二進制中1的個數(shù)

public static int binarySystem(int N){if(N%2!=0){return binarySystem(N/2)+1;}else {// 如果N為偶數(shù)，二進制中1的個數(shù)計算如下：int n;for ( n=0;N>0;n++){N&=(N-1);}return n;} }

直接進行計算，不適用遞歸的方式

/*** 由于n&(n-1)的這種方式可以直接計算，因此可以不用使用遞歸的方式操作* @param N* @return*/public static int binarySystem02(int N) {int n;for (n = 0; N > 0; n++) {N &= (N - 1);}return n;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/gosaint/p/8242862.html

總結(jié)

以上是生活随笔為你收集整理的java数据结构读书笔记--引论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。