递归

什么是递归？

递归，我们之前把它理解为函数调用函数它本身。
递归作为一种重要的编程思想。在二叉树、图或者一些高级的排序算法中，我们都会运用到递归。
所以，递归很重要！

一、我们首先来看一下递归的定义：

递归的能力在于用有限的语句来定义对象的无线集合。

问题规模较大时，递归和循环对比的话，递归比循环的代码量更少。

递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

函数在调用函数自身时，不能一直调用下去，否则会产生栈溢出的问题。

我们来总结一下，如下图：

递归分为递归前进段和递归返回段。
所以让我们通过例子来了解这两个概念。

二、下面让我再看一个新的概念“分治算法”

总结一下，分治算法就是当我们要处理的问题数据很多、步骤很麻烦的时候，我们可以先把它分解成几个子问题，如果子问题还较大就再分成更小的子问题。然后把这些子问题的解法组合成整个问题的解法。

我们举个例子来说明分治算法：

给定了需求：遍历一个文件夹中所有的文件。
当我们用以前的for循环来写的时候，因为我们不确定它要打开多少个文件夹，所以可能数量会很多，每次打开我们都要写for循环来进行遍历。这样的话，太过于繁琐了。

这个时候我们就可以用到分治算法。
我们的需求是遍历最上面的总文件夹中的文件。
我们用分治算法就是把它分成下一级的很多文件夹和文件。
把下一级的文件夹再分成下下一级的文件夹和文件。
通过这样的把大问题转换成一个个的小问题，这就叫做分治算法。

如果刚才那个例子太过抽象，那我们来看一下这个例子。

需求：在有序数组中查找指定元素

我们可以明显的看到这里的查找已经有了答案，运用的是二分查找法。
我们要在这个数组中找到数字“7”。
1.所以先把1-8分成两部分，1-4和5-8。
2.数字“7”在5-8的部分，所以再把5-8分为两部分。
3.经过这样的方法，我们就找到了最终指定的元素数字“7”。

通过上面这种解决题思路，就是把一个大的问题分成很多小问题。
这就是分治算法的体现。
虽然二分查找法是用循环写的。但此时我们的解题思路已经体现了分治算法。

	所以能用迭代写的，一定能用递归写。
	能用递归写的，不一定能用迭代写。
	迭代：迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。	

二、下面让我再看一个新的概念“回溯算法”

总结一下：回溯算法就是当我们在尝试寻找问题的解时发现不满足我们求解的条件，那么我们就“回溯”返回，直到找到符合求解条件的解。满足回溯条件的某个状态的点称为“回溯点”。
比如迷宫求解问题，当我们尝试走出迷宫时，发现我们现在所走的这条路线不通时，需要返回起始点继续重新选择路线。
这种思想的本质就是回溯算法。

经过对分治算法和回溯算法的解释。
我们可以总结一下递归。

递归就是先把大规模问题分成很多小问题，再把所有小问题的解组合起来。

三、下面我们来看一下递归的实际应用

题目让我们来求1加到n的值。
如果是以前我们肯定会采用for循环来把每个数字加起来然后求和。
或者是运用公式法求得总和。
而现在我们来运用递归的思想来解答这个题。
如图：

假设我们现在求1到100的和，那么我们可以把f(100)看成是f(99)+100,再把f(99)看成是f(98)+99…按照这样的思想，最终把这个问题分成了很多的小问题。

1.如图中的左边部分，绿色箭头一直指向下方，就是递归的前进段。
2.而右边的红色箭头一直指向上方，意为把每个小问题的值再整合起来往上传，其实就是递归的返回段。
这样我们就有了递归的前进段和返回段了，再加入判定前进或者返回的边界条件，就是一个完整的递归了。

让我们用代码实现：

public class RecursionDemo01 {
	public static void main(String[] args) {
		System.out.println(f(10));		//输出1到10的和
	}
	public static int f(int n){
		if(n==1){					//当n等于1时，只有1没有其他可以加的数字所以返回1
			return 1;
		}else{
			return f(n-1)+n;	//其他的情况返回f（n-1）+n的值
		}
	}

运行程序返回值如图：

答案正确！说明我们采用递归的思想解决问题是正确的！

递归的知识就到这里，通过不断的学习，我会进行补充。