java贪心算法几个经典例子_递归算法及经典递归例子代码实现

递归算法&＃xff08;英语&＃xff1a;recursion algorithm&＃xff09;在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题&＃xff0c;因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用&＃xff0c;在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环&＃xff0c;因此在很多函数编程语言&＃xff08;如Scheme&＃xff09;中习惯用递归来实现循环。

递归例子&＃xff1a;

&＃xff08;1&＃xff09;阶乘

n! &＃61; n * (n-1) * (n-2) * ...* 1(n>0)

&＃xff08;2&＃xff09;河内塔问题

&＃xff08;3&＃xff09;全排列

从n个不同元素中任取m&＃xff08;m≤n&＃xff09;个元素&＃xff0c;按照一定的顺序排列起来&＃xff0c;叫做从n个不同元素中取出m个元素的一个排列。当m&＃61;n时所有的排列情况叫全排列。

如1,2,3三个元素的全排列为&＃xff1a;

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

&＃xff08;4&＃xff09;斐波那契数列

斐波纳契数列&＃xff0c;又称黄金分割数列&＃xff0c;指的是这样一个数列&＃xff1a;1、1、2、3、5、8、13、21、……

这个数列从第三项开始&＃xff0c;每一项都等于前两项之和。

有趣的兔子问题&＃xff1a;

一般而言&＃xff0c;兔子在出生两个月后&＃xff0c;就有繁殖能力&＃xff0c;一对兔子每个月能生出一对小兔子来。如果所有兔子都不死&＃xff0c;那么一年以后可以繁殖多少对兔子&＃xff1f;

分析如下&＃xff1a;

第一个月小兔子没有繁殖能力&＃xff0c;所以还是一对&＃xff1b;

两个月后&＃xff0c;生下一对小兔子&＃xff0c;总数共有两对&＃xff1b;

三个月以后&＃xff0c;老兔子又生下一对&＃xff0c;因为小兔子还没有繁殖能力&＃xff0c;总数共是三对&＃xff1b;

……　

依次类推可以列出下表&＃xff1a;

//斐波那契
long Fib(int n)
{
if (n &＃61;&＃61; 0)
return 0;
if (n &＃61;&＃61; 1)
return 1;
if (n > 1)
return Fib(n-1) &＃43; Fib(n-2);
}

&＃xff08;4&＃xff09;判定一系列字符串中是否有相同的内容