一个方法体内调用它自身, 就称为递归方法. 方法递归包含了一种隐式的循环, 它会重复执行某段代码, 但这种重复执行无须循环控制.
要使用递归, 必须要有两个条件:
递归终止条件, 不然会陷入死循环
递归表达式, 即找出规律
下面, 给出几道关于递归的算法题, 来领悟递归的神奇.
1. 求 1~n 的阶乘
一般思路, 是用 for 循环来求解, 不过我们这里用递归来做.
- // 求 1~n 的阶乘
- public static int factorial(int n) {
- if (n == 1) {
- return 1;
- }
- return n * factorial(n - 1);
- }
2. 斐波那契数列 (Fibonacci sequence)
斐波那契数列的是这样一个数列: 1,1,2,3,5,8,13,21,34...., 即第一项 f(1) = 1, 第二项 f(2) = 1....., 第 n 项目为 f(n) = f(n-1) + f(n-2). 求第 n(n>=1) 项的值是多少.
- public static int fibonacci(int n) {
- if (n == 1) {
- return 1;
- } else if (n == 2) {
- return 1;
- } else {
- return fibonacci(n - 1) + fibonacci(n - 2);
- }
- }
3. 小青蛙跳台阶
一只青蛙一次可以跳上 1 级台阶, 也可以跳上 2 级. 求该青蛙跳上一个 n(n>=1) 级的台阶总共有多少种跳法.
- public static int frogJump(int n) {
- if (n == 1) {
- return 1;
- } else if (n == 2) {
- return 2;
- } else {
- return frogJump(n - 1) + frogJump(n - 2);
- }
- }
来源: https://www.cnblogs.com/sum-41/p/11267287.html