243e44b0c0b4be4f41dfd2b4ad258e8b
递归算法

1 引言

  程序调用自身的编程技巧称为递归( recursion)。递归作为一种算法在程序设计语言中广泛应用。 一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
  例如求和问题:若要求解S100 = 1+2+3+4+....+100的值,通过循环的方式代码如下:

int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum = sum + i;
}

  通过递归方式是如何求解呢?由1+2+3+4+....+100可以分解为(1+2+3+4+....+99) + 100,可以看出
  S100 = S99 + 100,可以得出Sn = Sn-1 + n。通过递归的方式代码如下:

public int sum(int n) {
    if (n == 1) {
        return 1;
    } else {
         return sum(n - 1) + n;
    }
}

  通过递归代码可以看出,sum()方法中又调用了其自身,只是将传入的参数发生改变。这种程序调用自身的方式就是递归。

2 应用场景

  什么样的问题才可以使用递归的方式求解呢?构成递归需要具备两个条件:
  (1)子问题与原始问题为同样的事情,二者的求解方法是相同的,且子问题比原始问题更易求解。
  (2)递归不能无限制地调用本身,必须有个递归出口。递归出口对应的情形相对简单,可以化简为非递归状况处理。

3 实例

3.1 斐波那契数列

  斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:
  1、1、2、3、5、8、13、21、34、……
  在数学上,斐波纳契数列以如下被以递推的方法定义:
  F(1)=1,F(2)=1,,F(n) = F(n-1) + F(n-2)(n>=3,n∈N*)

问题分析:
  斐波那契数列的对于原问题F(n)的求解可以转为对F(n-1)、F(n-2)两个子问题的求解,故符合条件(1)。由F(1)=1,F(2)=1,可以得出斐波那契数列问题是有递归出口的,递归出口对应F(1)=1,F(2)=1。求解斐波那契数列的代码如下:

```
public class FibonacciSequence {
public static void main(String[] args){
System.out.println(Fribonacci(9));

}
public static int Fribonacci(int n){
    if(n<=2)
        return 1;
    else
        return Fribonacci(n-1)+Fribonacci(n-2);

}

}

top Created with Sketch.