【算法】递归

递归的本质是方法不断调用本身。

我们知道for循环、while循环都是在代码块内部实现的，而在递归循环中，循环的是一个方法，即让方法不断自我循环。

但是不断循环会不断入栈，导致栈溢出。

为了解决这个问题，我们首先了解如何实现一个栈。

1、明确该递归的参数和返回值。

2、确定递归条件。

3、确定单层递归逻辑。

参数：算法中用到了哪些变量，哪些变量就是参数。

返回值：涉及加减乘除用int，其他一般用void。

例题一：斐波那契数列

package com.test;

public class Test {
	public static void main(String[] args) {
		int num = digui(9);
		System.out.println(num);
	}
	public static int digui(int n) {
		if (n == 1) {
			return 1;
		} else if (n == 2) {
			return 1;
		} else {
			return digui(n-1) + digui(n-2);
		}
	}
}

例题二：青蛙上台阶

package com.test;

public class Test {
	public static  void main(String[] args) {
		int num = jump(9);
		System.out.println(num);
	}
	public static int jump(int n) {
		if (n == 1) {
			return 1;
		}else if(n == 2) {
			return 2;
		}else {
			return jump(n-1) + jump(n-2);
		}
	}
}