日撸 Java 三百行： DAY16 递归

0.主题

今天学习递归，并使用递归的方法实现程序sumToN和fibonacci。

1.递归

当一个函数要用它自己来定义时，这个函数就被称之为递归的。对于一个递归求解的问题，每次递归调用求解一个和原问题相同但规模更小的问题，当问题足够小的时候，将直接返回答案，最终将会神奇的求解出原问题的答案。
对于递归程序，至少要求两点

• 基准情形：即base case，这种情形不需要再进行递归调用，可以直接返回答案
• 不断推进：即每次递归调用，程序应该朝着base case的方向靠近

当然还有其他的递归程序设计法则，但上面两条是最基本的。
以求解第 N N N个裴波那契数 F ( N ) F(N) F(N)为例，已知裴波那契数满足以下递推公式
F ( N ) = { F ( N − 1 ) + F ( N − 2 ) ,  N > 1 1 ,  N = 1 0 ,  N = 0 F(N)= \begin{cases}F(N-1)+F(N-2) &\text{, } N > 1 \\ 1 &\text{, } N = 1 \\ 0 &\text{, } N = 0 \end{cases} F(N)=⎩⎪⎨⎪⎧​F(N−1)+F(N−2)10​, N>1, N=1, N=0​
求 F ( N ) F(N) F(N)会调用 F ( N − 1 ) F(N - 1) F(N−1)与 F ( N − 2 ) F(N - 2) F(N−2)，则二者又会继续递归调用更小的子问题求解，当调用到 F ( 1 ) F(1) F(1)和 F ( 0 ) F(0) F(0)时，它们不再继续递归调用，而是直接返回答案，调用 F ( 1 ) F(1) F(1)和 F ( 0 ) F(0) F(0)得到答案后， F ( 3 ) F(3) F(3)也就得到了答案，最终还原到 F ( N ) F(N) F(N)，即得到最终的答案。

2.程序

1.sumToN
sumToN求解 0 \text{0} 0到 N \text{N} N的自然数之和，用递归的思维来解决它，很容易想到sumToN(N) = sumToN(N - 1) + N这个递推公式。对于base case，显然sumToN(0) = 0。因此就有了下方这个总的公式
s u m T o N ( N ) = { s u m T o N ( N − 1 ) + N ,  N ≥ 1 0 ,  N = 0 sumToN(N)= \begin{cases}sumToN(N-1)+N &\text{, } N\geq 1 \ 0 &\text{, } N = 0 \end{cases} sumToN(N)={sumToN(N−1)+N0​, N≥1, N=0​
有了这个递推公式，就可以写递归程序了，程序代码如下：

	/**
	 *********************
	 * Sum to N. No loop, however a stack is used.
	 * 
	 * @param paraN The given value.
	 * @return The sum.
	 *********************
	 */
	public static int sumToN( int paraN ) {
		if( paraN <= 0 ) {
			//Basis.
			return 0;
		} // Of if
		
		return sumToN( paraN - 1 ) + paraN;
	} // Of sumToN
	

时间复杂度： O ( n ) O(n) O(n)，有 T ( N ) = T ( N − 1 ) + 1 = T ( N − 2 ) + 2 = . . . = N T(N)=T(N-1)+1=T(N-2)+2=...=N T(N)=T(N−1)+1=T(N−2)+2=...=N故可以看出该程序时间复杂度为 O ( n ) O(n) O(n)。

空间复杂度： O ( n ) O(n) O(n)，递归执行时，隐式的维护一个栈，该程序要一直递归调用到sumToN(1)才会d栈，故空间复杂度 O ( n ) O(n) O(n)。

2.fibonacci
fibonacci的递推公式已经在上文叙述过，此处不再赘述，直接代码附上：

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

3.测试
测试代码如下：

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main( String args[ ] ) {
		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

测试结果如下：

3.体会

1. 递归程序关键要分析清楚两个问题。一是原问题与递归调用的子问题之间的关系，二是有哪些无需继续递归而可直接给出答案的基准情形。
2. 递归程序简洁明了，能清晰体现程序设计的逻辑。
3. 递归程序的效率可能不一定高，比如递归求解裴波那契数的时间复杂度是指数级的，这是因为递归过程中进行了许多重复的计算导致的效率低下。
4. 递归程序的时间复杂度计算要比非递归程序更复杂，通常需要先写出递归关系的方程然后再求解。