java递推算法-“Fibonacy数列和汉诺塔问题”的基本思想是已“以此类推”

首先说一下什么是递归，递归是解决逻辑或数学问题的一种方法，他通常把一个复杂的问题层层转化为一个或者多个性质相同但是规模很小的问题来求解，其基本思想是已“以此类推”。在学习“Fibonacy数列和汉诺塔问题”之前先看一个用递归方式计算整数阶乘的例子java递推算法，以此说明递归算法中的一些概念：

递归计算4的阶乘：

public class Factorial{

public int f(int n){

if(n==1){ //这里就是所谓的递归头

return 1;

}else{

int k=f(n-1); //这个就是递推公式

return n*k;

}

}

public static void main(String []args){

Factorial fact=new Factorial();

int result=fact.f(4);

System.out.println(result);

}

}

最后运行的结果为“24”，正确。

一个递归算法里面需要有两个语句，一个是“递归头”，递归头的含义可以理解为：复杂问题最简单的形式表现。如上例计算4的阶乘问题可以转化为最简单的问题-------计算1的阶乘(就是上例中的if(n==1){return 1;}语句所表达的含义)；另一个是”递推公式“，比如上例中的int k=f(n-1) 就是一个递推公式。只有确定了正确的递归头和递推公式，程序才会正确的执行。

下面来看一个经典的递归例子(Fibonacy数列问题)问题的描述是：一个数等于其前面相邻的两个数的和，具体描述公式如下： a1=1,a2=1;an=an-1+an-2。代码如下：

public class TestFibonacty{

public static void main(String []args){

TestFibonacty t=new TestFibonacty();

System.out.println(t.m1(40))

}

public int m1(int n){

int p1=1,p2=1,c=0;//p1表示第一个数，p2表示第二个数java递推算法，c表示两个相邻的数的和

if(n==1||n==2){ //递归头

return 1;

}else{

int result=m1(n-1)+m2(n-2); //递推公式

return result;

}

}

}