算法之递归

递归本质：递归是一段程序的代码反复效用，把程序的参数等变量保存在一个堆栈里， 直到到了边界条件以后再层层返回，将堆栈中的数据弹出计算，最后得到结果。

递归满足的三个条件：
1：一个问题的解可以分为几个子问题的解
2：这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3：存在递归终止条件

递归的例子：斐波那契数列
这样一个数列：0、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)，终止条件就是F(1)=1，F(2)=1。

使用递归实现斐波那契数列：

package 递归;
public class FibonacciSequence {
public int f(int step) {
		if (step==1) {
			return 1;
		} else if (step==2) {
			return 1;
		} else {
			return f(step-1)+f(step-2);
		}
	}
	public static void main(String[] args) {
		FibonacciSequence fibonacciSequence = new FibonacciSequence();
		System.out.println(fibonacciSequence.f(5));
	}
}

递归代码也有很多弊端，比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等。
在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

本文地址：https://blog.csdn.net/weixin_43894879/article/details/107359741