读题

递归，就是运行时候自己调用自己，最近写到一个递归算法时，想知道程序具体运行的顺序。查看了一些资料，推荐这篇文章《简单易懂的现代魔法_递归》，有动图，易于理解。

递归，最重要的两点：

1. 有明确的终止条件，防止无限循环；
2. 有递归函数，保证自己能够调用自己

递归函数在实现的过程中，是一个调用栈的过程。栈是一种后进后出式的数据结构，数据在表的同一端压入（PUSH）或者弹出（POP）。函数在调用另一个函数时，当前函数会处于暂定、未完成的状态，暂停函数的所有变量的值仍然会保存在内存中，直到函数执行完毕，所占内存会被弹出栈。

下面是一个递归代码以及运行结果，加了一些输出语句，帮助看清执行顺序。

问题描述：
用递归的方法求整数的N次方，代码如下：

public class NPower {
	public double expCalculate(int x,int n) {
		 double y;
		 int m = n >> 1;
		 System.out.println("n = "+n + ", m = "+m);
		 if(n == 0) 
			 return 1;
		 else {
			 y = expCalculate(x,m);
			 System.out.println("y1 = " + y);
			 y = y * y;
			 System.out.println("y2 = " + y +", n = "+n);
			 if(n % 2 == 1) {
				 y = y * x;
				 System.out.println("n = "+n+", y = "+y+", x = "+x);
			 }
		 }
		 return y;
	}
	public static void main(String[] args) {
		NPower res = new NPower();
		System.out.println(res.expCalculate(3, 5));
	}
}

输出的结果是：

n = 5, m = 2
n = 2, m = 1
n = 1, m = 0
n = 0, m = 0
y1 = 1.0
y2 = 1.0, n = 1
n = 1, y = 3.0, x = 3
y1 = 3.0
y2 = 9.0, n = 2
y1 = 9.0
y2 = 81.0, n = 5
n = 5, y = 243.0, x = 3
243.0

调用栈

递归函数是y = expCalculate(x,m)， 如要求3^5的值，即在主函数调用时输入参数为(3,5)，这个递归函数会被调用4次，对应着输出结果的前4行，每次都会储存函数的一个变量n的值，用于之后代码的执行。

入栈

第一次函数调用，y = expCalculate(3,5)，n = 5，但是函数还要调用自身，所以y = expCalculate(3,5)这一部分未完成，被压入栈中，连同变量n = 5一起被保存；然后执行y = expCalculate(3,2)，n = 2，未到终止条件，将这一状态以及变量n的值继续压入栈中；然后是y = expCalculate(3,1)，n = 1，入栈；然后是y = expCalculate(3,0)，n = 0，满足终止条件，return y = 1。
为了方便展示，我做了一个视频，表示不同调用阶段时函数和储存的变量值。
这个是入栈的顺序，每次调用下一个函数时，之前未完成的函数和参数都会入栈存储。直到递归终止条件（n = 0），return y = 1 ，递归函数开始出栈，计算之前未完成的函数部分。

出栈

• 接下来执行y = expCalculate(3,1)的剩余部分，y = y * y = 1，n是奇数，执行y = y * x =3，return y = 3，y = expCalculate(3,1) 部分完成，弹出；
• 接下来执行y = expCalculate(3,1)的剩余部分，y = y * y = 1，n是奇数，执行y = y * x =3，return y = 3，y = expCalculate(3,1) 部分完成，弹出；
• 接下来执行y = expCalculate(3,2)的剩余部分，y = y * y = 9，n = 2是偶数，return y = 9，y = expCalculate(3,2) 部分完成，弹出；
• 然后执行y = expCalculate(3,5)的剩余部分，y = y * y = 81，n = 5是奇数，执行y = y * x =243，return y = 243，y = expCalculate(3,5) 部分完成，弹出。
• main函数中的整个res.expCalculate(3, 5)调用完毕，返回值为243。
• 整个递归函数调用完毕。

完整调用示意图

我把视频转换为一个gif图，虽然有点卡顿，不过还是能看出整体的过程。（如果需要原视频，可以评论或私信我）

感想

递归会降低程序性能，而且嵌套太深会形成很长的栈，占用大量内存。
学习递归需要反复思考，抓住深层原理，加油！