今天学习递归，并使用递归的方法实现程序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)，即得到最终的答案。
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{, } Ngeq 1 \ 0 &text{, } N = 0 end{cases}
sumToN(N)={sumToN(N−1)+N0, N≥1, N=0
有了这个递推公式，就可以写递归程序了，程序代码如下：
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)才会弹栈，故空间复杂度 O ( n ) O(n) O(n)。
2.fibonacci
fibonacci的递推公式已经在上文叙述过，此处不再赘述，直接代码附上：
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.测试
测试代码如下：
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
测试结果如下：
- 递归程序关键要分析清楚两个问题。一是原问题与递归调用的子问题之间的关系，二是有哪些无需继续递归而可直接给出答案的基准情形。
- 递归程序简洁明了，能清晰体现程序设计的逻辑。
- 递归程序的效率可能不一定高，比如递归求解裴波那契数的时间复杂度是指数级的，这是因为递归过程中进行了许多重复的计算导致的效率低下。
- 递归程序的时间复杂度计算要比非递归程序更复杂，通常需要先写出递归关系的方程然后再求解。
