[Java知识库]递归java

本质

1. 递归就是自己调用自己的过程。
2. 系统会为递归建栈, 这个需要理解一下. 例如, 累加程序, 空间复杂度是 O ( n ) O(n)O(n), 因为只有运行到 paraN = 1 时, 才会弹栈.

?递归求和:

public class Recursion {
    public static int sumToN(int paraN) {
    	if(paraN<=0) {
    		//Basis.
    		return 0;
    	} // of if
    	return sumToN(paraN-1)+paraN;
    }// of sumToN

?Fibonacci:

	/*
	 * Fibonacci sequence.
	 * 
	 * @param paraN The given value.
	 * 
	 * @return The sum.
	 */
    public static int fibonacci(int paraN) {
    	if(paraN<=0) {
    		//Negative values are invalid.Index 0 corresponds to the first element
    		return 0;
    	} if (paraN==1) {
    		//Basis.
    		return 1;
    	}//of if
    	return fibonacci(paraN-1)+fibonacci(paraN-2);
    }//of fibonacci

整体代码:

/**
 * 
 */
package pt;

/**
 * @author lenovo
 *
 */
public class Recursion {
    public static int sumToN(int paraN) {
    	if(paraN<=0) {
    		//Basis.
    		return 0;
    	} // of if
    	return sumToN(paraN-1)+paraN;
    }// of sumToN
    
	/*
	 * Fibonacci sequence.
	 * 
	 * @param paraN The given value.
	 * 
	 * @return The sum.
	 */
    public static int fibonacci(int paraN) {
    	if(paraN<=0) {
    		//Negative values are invalid.Index 0 corresponds to the first element
    		return 0;
    	} if (paraN==1) {
    		//Basis.
    		return 1;
    	}//of if
    	return fibonacci(paraN-1)+fibonacci(paraN-2);
    }//of fibonacci
	/*
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 */
    public static void main(String arg[]) {
    	int tempValue=5;
    	System.out.println("0 sum to "+ tempValue +" = "+sumToN(tempValue));
    	
    	tempValue =-1;
    	System.out.println("0 sum to "+ tempValue +" = "+sumToN(tempValue));
    	
    	for(int i=0;i<10;i++) {
    		System.out.println("Fibonacci "+i+": "+fibonacci(i));
    	}//of for i
    	
    	
    }// of main
}// of class Recursion

? 读者可以简单看下代码，代码不难，可以理解到递归的本质最好，其实汉诺塔问题也是经典的递归，但它更多的是对形参/实参的理解, 所以不写在这里给读者添堵. 再说了, 那种极端的例子也不具有代表性.