关于递归的理解
1.递归的理解
1）递归的概念
一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的 。
古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象 。
通俗来说就是一种形式，不断调用一个函数，如在点外卖时候，会点开炒饭区如果没有想要吃的，就点开煮面区，一直重复到点好外卖为之 。
2）递归的三大要素
①明确函数要干什么
对于递归，我觉得很重要的一个事就是，这个函数的功能是什么，要完成什么样的一件事，而这个，是完全由自己来定义的。也就是说，先不管函数里面的代码什么，而是要先明白，这个函数是要用来干什么。
我们定义了一个算n的阶乘的函数，
传入是一个int型整数，输出也是一个int型整数
功能就是计算n的阶乘
int f（int n）{
计算n的阶乘；
return n的阶乘；
}
②寻找递归结束条件
所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然会一直调用自己，直到栈溢出。也就是说，我们需要找出参数变化为何值时的条件使得递归结束，再把结果返回，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
先拆分为几小步
int f（int n）{
//当传入的是1，我们能很清楚知道1的阶乘是1
if(n == 1){
return 1;
}
//当传入的是2，我们能很清楚知道2的阶乘是2*1=2
if(n == 2){
return 2*1;//等价于return 2;
}
//当传入的是3，我们能很清楚知道2的阶乘是3*2*1=6
if(n == 3){
return 3*2*1;
}
//结合一下找到递归结束的条件就是n<=2
if(n <= 2){
return n;
}
}
③找出函数的等价关系式
我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
例如，f(n) 这个范围比较大，我们可以让 f(n) = n * f(n-1)。
这样，范围就由 n 变成了 n-1 了，范围变小了
并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。
也就是要找到原函数的一个等价关系式
f(n) 的等价关系式为 n * f(n-1)，即f(n) = n * f(n-1)。
int f（int n）{
//结合一下找到递归结束的条件就是n<=2
if(n <= 2){
return n;
}
//把f(n)的等价操作写进来
return f(n-1)*n;
}
就这样递归三要素已经都写进代码里了，所以这个 f(n) 功能的内部代码我们已经写好了。
这就是递归最重要的三要素，也就是每次做递归的时候，可以试着去寻找这三个要素。
④举些例子
各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
将用栈解决的问题–>递归代码比较简洁
1.斐波那契数列
问题：斐波那契数列的是这样一个数列：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的阶乘的函数，
传入是一个int型整数，输出也是一个int型整数
功能就是求第n项的值
int f（int n）{
计算第n项的值；
return 第n项的值；
}
第二步找出递归结束的条件
int f（int n）{
//当传入的是1，我们能很清楚知道求第1项的值是1
if(n == 1){
return 1;
}
//当传入的是1，我们能很清楚知道求第2项的值是1
if(n == 2){
return 1;
}
//当传入的是3，我们能很清楚知道第3项的值是2
if(n == 3){
return 2;
}
//结合一下找到递归结束的条件就是n<=2
if(n <= 2){
return 1;
}
}
第三步，找出函数等价条件关系式
题目已经把等价关系式给我们了，很容易就能够知道 f(n) = f(n-1) + f(n-2)。
int f（int n）{
//结合一下找到递归结束的条件就是n<=2
if(n <= 2){
return 1;
}
//加入等价式
return f(n-1) + f(n - 2);
}
2.小青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
第一步，写出递归函数和功能
我们定义了一个算n的阶乘的函数，
传入是一个int型整数，输出也是一个int型整数
功能就是求青蛙跳上一个n级的台阶总共有多少种跳法
int f（int n）{
青蛙跳上一个n级的台阶总共有多少种跳法；
return 青蛙跳上一个n级的台阶总共有多少种跳法；
}
第二步找出递归结束的条件
int f（int n）{
//当传入的是1，我们能很清楚知道求青蛙跳上一个1级的台阶总共有1种跳法
if(n == 1){
return 1;
}
//当传入的是1，我们能很清楚知道求青蛙跳上一个2级的台阶总共有2种跳法
if(n == 2){
return 2;
}
//当传入的是3，我们能很清楚知道求青蛙跳上一个3级的台阶总共有3种跳法
if(n == 3){
return 3;
}
//结合一下找到递归结束的条件就是n==1
if(n == 1){
return 1;
}
}
第三步，找出函数等价条件关系式
每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。
第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。
等价关系式就求出来了
int f（int n）{
//结合一下找到递归结束的条件就是n<=2
if(n == 1){
return 1;
}
//加入等价式
ruturn f(n-1) + f(n-2);
}
这时候问题来了，n=2时，会有f(2) = f(1) + f(0)，f(0)=0,
按道理是递归结束，不用继续往下调用的
但我们上面的代码逻辑中，会继续调用 f(0) = f(-1) + f(-2)。
这会导致无限调用，从而进入死循环。
也就是说，我们要补上n=0的条件
int f(int n){
//经过分析，f(2)=2也是一个临界条件。
if(n <= 2){
return n;
}
ruturn f(n-1) + f(n-2);
}
3.反转单链表
问题：反转单链表。例如链表为：1->2->3->4。反转后为 4->3->2->1
第一步，写出递归函数和功能
我们定义了一个算n的阶乘的函数，
传入是一个单链表头节点，输出也是一个单链表头节点
功能就是反转单链表
先来个链表节点
class Node{
Object date;
Node next;
}
Node f（Node head）{
反转单链表；
return 反转后的单链表节点；
}
第二步找出递归结束的条件
容易可以得出链表只有一个节点或者是一张空表时候结束递归
Node f（Node head）{
if(head == null || head.next == null){
return head;
}
}
第三步，找出函数等价条件关系式
2->3->4 递归成 4->3->2。1这个节点我们并没有去碰它，所以1的next节点仍然是连接2。
只需要把节点2的next指向1，然后把1的next指向 null就行了。
f(head) 等价于 f(head.next) + 改变一下1，2两个节点的指向。
Node f（Node node）{
if(head == null || head.next == null){
return head;
}
//递归反转子链表
Node newList = f(head.next);
//改变 1，2节点的指向。
//通过 head.next获取节点2
Node t1 = head.next;
//让2的next指向2
t1.next = head;
//1的next指向null.
head.next = null;
//把调整之后的链表返回。
return newList;
}
2.递归之八皇后问题理解
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线上，
问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，
后来有人用图论的方法解出92种结果。
计算机发明后，有多种计算机语言可以解决此问题
八皇后问题是典型的回溯法解决的问题。
所谓回溯法，名字高大上，思想很朴素。设想把你放在一个迷宫里，想要走出迷宫，最直接的办法是什么呢？没错，试。先选一条路走起，走不通就往回退尝试别的路，走不通继续往回退，直到找到出口或所有路都试过走不出去为止。这就是暴力破解。盲僧李青说得好：如果暴力不是为了解题，那就毫无意义了。
尽管回溯法也算是暴力方法，但也不是特别暴力
从8*8=64个格子里选8个格子，放皇后，测试是否满足条件，若满足则计数加1，否则换8个格子继续试。
很显然， 64中选8，并不是个小数字，有着十亿级别的尝试次数
稍加分析，我们可以得到一个不那么暴力的办法，显然，每行每列最多只能有一个皇后，如果基于这个事实进行暴力破解，那结果会好得多。安排皇后时，第一行有8种选法，一旦第一行选定，假设选为（1，i），第二行只能选（2，j），其中j!=i，所以有7种选法。以此类推，需要穷举的情况有8！=40320种。
看起来这个结果已经不错了，但尝试的次数是随问题规模按阶乘水平提高的，8皇后太多了，把问题缩成4皇后，4个皇后在4*4的格子里各自安排不打架，一共有多少种安排方法？
试着穷举，4！=24次，我们真的需要24次尝试吗？
现在我们把第一个皇后放在第一个格子，被涂黑的地方是不能放皇后的。
第二行的皇后只能放在第三格或第四格，比方我们放第三格，则：
前两位皇后沆瀣一气，已经把第三行全部锁死了，第三位皇后无论放哪里都难逃被吃掉的厄运。于是在第一个皇后位于1号，第二个皇后位于3号的情况下问题无解。我们只能返回上一步来，给2号皇后换个位置。
显然，第三个皇后只有一个位置可选。当第三个皇后占据第三行蓝色空位时，第四行皇后无路可走，于是发生错误，返回上层调用（3号皇后），而3号也别无可去，继续返回上层调用（2号），2号已然无路可去，继续返回上层（1号），于是1号皇后改变位置如下，继续搜索
到这，“回溯法”便是谓知易行难
基本思路是：
1.第一行先占一个皇后
2.第二行再占一个且不能与第一个皇后攻击
3.第三行再占一个
…
n.第n行占一个，当第n行站不下的时候，取消n-1行的皇后，在第n-1皇后的下一个位置重新占一个皇后位置，知道占到最n-1行的最后一个位置，当还不行的时候，就取消第n-2行，当n-2行的皇后在n-2行的最后一个位置的时候，就取消n-3，n-2在最后一个位置，那么n-3行的一定不再最后一个位置
再重新寻找n-2行的皇后的位置
…
直到找到最后一个皇后
package com.atguigu.queen8;
public class Queen8 {
// 一共有多少个皇后（此时设置为8皇后在8X8棋盘）
int max = 8;
// 该数组保存结果，第一个皇后摆在array[0]列，第二个摆在array[1]列
int[] array = new int[max];
static int count = 0;
public static void main(String[] args) {
Queen8 queen8 = new Queen8();
queen8.check(0);
System.out.println("一共有" + count + "种解法");
}
/**
* n代表当前是第几个皇后 [n 是从 0 开始算的，即0 表示第一个皇后, 同时n也表示第几行]
* 即 第1行是第一个皇后(n=0)，第2行是第二个皇后(n=1), 第8行是第8个皇后(n=7)，如果遍历到第9行(n=8)，说明
* 皇后全部放置好了, 就相应的得到了一种解法...
* 然后回溯 ，又将第一个皇后，放置第1行的第2列...
* @param n
* 皇后n在array[n]列
*/
private void check(int n) {
//终止条件是最后一行已经摆完，
//由于每摆一步都会校验是否有冲突，
//所以只要最后一行摆完，说明已经得到了一个正确解
if (n == max) {
print();
return;
}
//将第n个皇后从.第一列开始放值，然后判断是否和本行本列本斜线有冲突，如果OK，就进入下一行的逻辑
for (int i = 0; i < max; i++) {
array[n] = i; //先将第一个皇后放置第一行的第一列 array[0] = 0
if (judge(n)) { // 如果 该皇后没有和其它皇后冲突
check(n + 1); // 放第二个皇后，因为是递归，因此大家可以思考，第二个皇后是从 第二行的第1列开始放
}
}
}
/**
* 查看n皇后是否满足约束条件(即：检查皇后n是否会发生冲突)
* 如果冲突，返回 false , 如果不冲突返回true
* 0 4 7 5 2 6 1 3
* @param n
* @return
*/
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
//说明:
//1. array[i] == array[n] 判断 是不是在同一列
//2. Math.abs(n - i) == Math.abs(array[n] - array[i]) 判断是不是在同一条斜线
//3. 不用判断是不是在同一行，因为我们每放一个皇后，行是递增的.
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
/**
* 打印这个满足条件的八皇后的放置位置
*/
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
3.递归的优化
递归的优点：
书写：简洁
使用：在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
递归的缺点：
性能：假设传入的参数值特别大，那么这个调用栈将会非常之大，最终可能超出调用栈的缓存大小而崩溃导致程序执行失败。每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。
效率：
递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。
递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。
1）尾调用
尾递归是一种递归的写法，可以避免不断的将函数压栈最终导致堆栈溢出。通过设置一个累加参数，并且每一次都将当前的值累加上去，然后递归调用。通过尾递归，我们可以把复杂度从O(n)降低到O(1)，是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。
(注意：**JVM仍然不支持尾调用优化，**因此对大多数Java开发人员来说，Java不进行尾调用优化并不是什么大问题。不过我猜或许很多Java程序员都没有听说过尾调用优化这回事。不过当你在JVM上运行函数式语言的话，这就成为一个问题了。递归的代码在自己语言的解释器里运行得好好的，可能一到JVM上就突然把栈给用完了。)
以下用js代码为例
//核心：就是看一个函数在调用另一个函数得时候，本身是否可以被“释放”
function f(x) {
a(x)
b(x)
return g(x) //函数执行的最后调用另一个函数
}
任何的尾调用，不只是尾递归，函数调用本身都可以被优化掉，变得跟goto操作一样。这就意味着，在函数调用前先把栈给设置好，调用完成后再恢复栈的这个操作（分别是prolog和epilog）可以被优化掉。比如说下面的这段代码：
函数调用栈和调用帧为例
函数的调用层数非常多时，调用栈会消耗大量内存，甚至栈溢出，造成程序严重卡顿或意外崩溃。
function f(x) {
res = g(x)
return res+1
}
function g(x) {
res = r(x)
return res + 1
}
function r(x) {
res = x + 1
return res + 1
}
尾调用解决栈溢出风险
调用g之后，和f就没有任何关系了，函数f就结束了，
所以执行到最后一步，完全可以删除 f() 的调用记录，
只保留 g(30) 的调用记录。
function f() {
m = 10
n = 20
return g(m + n)
}
f()
// 等同于
function f() {
return g(30)
}
f()
// 等同于
g(30)
将函数优化为尾调用，那么完全可以做到每次执行时，调用帧为一，这将大大节省内存，提高能效。
说到递归,尾递归=尾调用+递归
function factorial(n, total = 1) {
// console.trace()
if (n === 0) {
return total
}
return factorial(n - 1, n * total)
}
调用如下
factorial(3, 1)
factorial(2, 3)
factorial(1, 6)
factorial(0, 6)
// n = 0; return 6
调用栈不再需要多次对factorial进行压栈处理，因为每一个递归调用都不在依赖于上一个递归调用的值。因此，空间的复杂度为o(1)而不是0(n)。
2）memoization
（引自https://www.cnblogs.com/lalalagq/p/9906621.html）
简单来说，memoization 是一种优化技术，主要用于通过存储昂贵的函数调用的结果来加速计算机程序，并在再次发生相同的输入时返回缓存的结果。
不使用 memoization
不假思索，我们会立即写下如下的代码：
const factorial = n => {
if (n === 1) {
return 1
} else {
return factorial(n - 1) * n
}
};
使用memoization
const cache = []
const factorial = n => {
if (n === 1) {
return 1
} else if (cache[n - 1]) {
return cache[n - 1]
} else {
let result = factorial(n - 1) * n
cache[n - 1] = result
return result
}
};
使用 闭包 和 memoization
常见的方式是 闭包 和 memoization 一起搭配使用：
const factorialMemo = () => {
const cache = []
const factorial = n => {
if (n === 1) {
return 1
} else if (cache[n - 1]) {
console.log(`get factorial(${n}) from cache...`)
return cache[n - 1]
} else {
let result = factorial(n - 1) * n
cache[n - 1] = result
return result
}
}
return factorial
};
const factorial = factorialMemo();
memorization 可以把函数每次的返回值存在一个数组或者对象中，在接下来的计算中可以直接读取已经计算过并且返回的数据，不用重复多次相同的计算。是一个空间换时间的方式，这种方法可用于部分递归中以提高递归的效率。
3）函数式编程（Java描述）：尾调用及抽象递归
一个有趣的解释，递归就是包子馅的包子，它的极限是个馒头。即便Java不支持尾调用优化，但我们并不想浪费尾递归带来的便利，《Java函数式编程》一书提供了一个非常好的思路，把递归进一步抽象出来，将在栈上的递归改为在堆上的递归。
public static int sum(int n, int acc) {
if (n == 0){
return acc;
}
else {
acc = acc + n;
return sum(n - 1, acc);
}
}
这是一个符合尾递归的函数
但把参数给个1000，会爆栈
只是因为Java不支持尾调用优化，也就是jvm虚拟机不支持这个。
现在，我们来进一步抽象递归操作。
我们定义一个类TailCall来表示递归操作，其中泛型T表示递归操作的结果类型。递归分为两个部分，一个是中间调用，另一个就是最终结果，因此我们需要两个子类表示这些过程。即用Return表示最后一个调用，它是提供结果的，所以直接持有一个T类型的变量；Suspend表示中间的递归调用，为我们提供调用链上的某一部操作，持有Supplier实例。很明显，这是一个用链表表示的栈结构（LIFO）,每一个节点存储每一步调用步骤。
public abstract class TailCall<T> {
private TailCall() {
}
public static class Return<T> extends TailCall<T> {
private final T t;
public Return(T t) {
this.t = t;
}
}
public static class Suspend<T> extends TailCall<T> {
private final Supplier<TailCall<T>> resume;
public Suspend(Supplier<TailCall<T>> resume) {
super();
this.resume = resume;
}
}
}
我们抽象出几个方法来表示这两个子类的操作：
public abstract TailCall<T> resume();
//返回调用链上的某一中间步骤
public abstract T eval();
//返回结果
public abstract boolean isSuspend();
//是否是一个中间操作
对于Return类来说：
@Override
public TailCall<T> resume() {
throw new IllegalStateException("return has no resume!");
}
//我表示的是一个最终调用产生的结果，所以我没必要支持此操作，直接抛出异常。
@Override
public T eval() {
return t;
}
//返回储存的结果
@Override
public boolean isSuspend() {
return false;
}
//我不是一个中间调用过程，返回false。而对于Suspend类：
@Override
public TailCall<T> resume() {
return resume.get();
}
//返回调用链的下一个TailCall.
@Override
public T eval() {
TailCall<T> tailCall = this;
while (tailCall.isSuspend()) {
tailCall = tailCall.resume();
}
return tailCall.eval();
}
//通过不断在调用链上遍历，找到最终的结果。
@Override
public boolean isSuspend() {
return true;
}
//Suspend表示我是一个中间操作
完整代码
public abstract class TailCall<T> {
public abstract TailCall<T> resume();
public abstract T eval();
public abstract boolean isSuspend();
private TailCall() {
}
public static <T> Return<T> ret(T t) {
return new Return<T>(t);
}
public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {
return new Suspend<>(s);
}
public static class Return<T> extends TailCall<T> {
private final T t;
public Return(T t) {
this.t = t;
}
@Override
public TailCall<T> resume() {
throw new IllegalStateException("return has no resume!");
}
@Override
public T eval() {
return t;
}
@Override
public boolean isSuspend() {
return false;
}
}
public static class Suspend<T> extends TailCall<T> {
private final Supplier<TailCall<T>> resume;
public Suspend(Supplier<TailCall<T>> resume) {
super();
this.resume = resume;
}
@Override
public TailCall<T> resume() {
return resume.get();
}
@Override
public T eval() {
TailCall<T> tailCall = this;
while (tailCall.isSuspend()) {
tailCall = tailCall.resume();
}
return tailCall.eval();
}
@Override
public boolean isSuspend() {
return true;
}
}
}
public static int sum(int n, int acc) {
return sum0(n, acc).eval();
}
public static TailCall<Integer> sum0(int n, int acc) {
return n == 0 ? ret(acc) : sus(() -> sum0(n - 1, acc + n))；
//将两个工厂方法静态导入
}
尽管可以，当使用函数式语言在JVM上进行开发的时候，也要避免使用过深的递归调用。
4.递归的调用机制（简单版）
如图所示：当调用test(4)方法时，会在栈内存中独立开辟一个新的栈，接着调用test(4)方法时会再独立开辟一个新的栈直到不需要再次调用。
可以看到，一个函数每次被调用时，都会在内存中创建一个帧，来包含函数的局部变量和参数，对于递归函数，栈上可能同时存在多个函数帧。当每调用一次函数f(n)时，栈顶指针就会往栈顶移动一个位置，直到满足退出递归的条件（n==1）.之后再依次返回当前的结果直接，栈顶指针往下移动。
递归，也就是先“递”后“归”。
这时要说到递归的调用规则
-
程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈) 。
-
函数的局部变量是独立的，不会相互影响 。
-
递归必须向退出递归的条件逼近，否则就是无限递归 。
-
当一个函数执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁 。
例：
求函数值：
已知 f(1)=3; f(n) = 2*f(n-1)+1; 请使用递归的思想编程，求出f(n)的值.
用递归来做的话便是：
f(4)=2 * f(3) + 1
f(4)=2 * (2 * f(2) + 1) + 1
f(4)=2 * (2 * (2 * f(1) + 1) + 1) + 1
f(4)=2 * (2 * (2 * 3 + 1) + 1) + 1
f(4)=2 * 15 + 1
f(4)=31
5.递归的调用机制（复杂版）
1）基于栈的本质
（引自：https://blog.csdn.net/dashuniuniu/article/details/50347149）
例如执行”a = b + c”，在基于栈的虚拟机上字节码指令如下所示：
I1: LOAD C
I2: LOAD B
I3: ADD
I4: STORE A
由于操作数都是隐式地，所以指令可以做的很短，一般都是一个或者两个字节。但是显而易见就是指令条数会显著增加。而基于寄存器虚拟机执行该操作只有一条指令：
I1: add a, b, c
其中a，b，c都是虚拟寄存器。操作数栈上的变化如下图所示：
首先从符号表上读取数据压入操作数栈，
然后从栈中弹出操作数执行加法运算，这步操作有物理机器执行，如下图所示：
2）递归的工作栈
（引自https://www.cnblogs.com/yangyuliufeng/p/9211412.html）
IA-32使用栈来支持过程的嵌套调用。每个过程都有自己的栈区，称为栈帧（stack frame） 。因此，一个栈由若干栈帧组成，每个栈帧用专门的帧指针寄存器EBP指定起始位置，当前栈帧的范围在其和栈指针寄存器ESP指向区域之间。
IA-32规定，寄存器EAX、ECX和EDX是调用者保存寄存器。当过程P调用过程Q时，Q 可以直接使用这三个寄存器，不用将它们的值保存到栈中，这也意味着，如果P在从Q返回后还要用这三个寄存器的话，P应在转到Q之前先保存它们的值，并在从Q返回后先恢复它们的值再使用。寄存器EBX、ESl、EDI是被调用者保存寄存器，Q必须先将它们的值保存到栈中再使用它们，并在返回P之前先恢复它们的值。
（1）每次递归调用前，先将参数n~参数1按序复制到调用过程栈帧中
（2）执行call指令：首先将返回地址（call指令要执行时EIP的值，即call指令下一条指令的地址）压入栈顶，然后将程序跳转到当前调用的方法的起始地址，相当于执行了push和jump指令。
递归调用时，每一层调用过程栈帧中存放的返回地址都是相同的。
（3）每次递归，必定要先push %ebp（把原帧指针保存在栈顶）和mov %esp,%ebp（把存放原帧指针的栈顶，设置为新栈底）
被调用者定义的非静态局部变量仅存放于当前栈帧，调用结束后就被释放了。
最后往往通过EAX寄存器将结果返回给调用者。
（4）执行leave指令：将栈指针指向帧指针，然后pop备份栈顶存放的原帧指针到EBP。
（5）最后执行ret指令：将栈顶的返回地址弹出到EIP，然后按照EIP此时指示的指令继续执行程序。
如图所示，Q的过程体执行时，入口参数1的地址总是R[ebp]+8，入口参数2的地址总是R[ebp]+12……（在栈中传递的参数若是基本类型，则都被分配4个字节）
与IA-32不同，x86-64最多可有6个整型或指针型参数通过寄存器传递，超过6个入口参数时，后面的通过栈来传递。在栈中传递的参数若是基本类型，则都被分配8个字节。栈中的地址也变为了8个字节。
RAX、R10和R11为调用者保存寄存器。RBX、RBP、R12、R13、R14和R15为被调用者保存寄存器，需要将它们先保存在栈中再使用，最后返回前再恢复其值。
过程调用中使用的栈机制和寄存器使用约定，使得可以进行过程的嵌套调用和递归调用。
3）递归的底层
（以下转载于https://www.cnblogs.com/syw-casualet/p/5223595.html）
以c和汇编的程序为例
pushl %ebp //压栈，压入一个栈顶元素并存到寄存器ebp中
movl %esp, %ebp //将ebp内存单元中的数据传给esp，让esp = ebp，栈顶指针等于栈底指针
subl $4, %esp //esp=esp-4，即esp向下移动4个单位，相当于开辟了1个局部int，同时默认了ebp为栈底
这三条用于保存栈的信息，ebp寄存器指向栈底，esp寄存器指向栈顶，栈底是高地址而栈底是低地址。执行完这三行后，栈就为main开辟了一个新空间，新空间从ebp开始到esp结束。
开辟前与开辟后寄存器的位置关系如下图：
当main执行完后，我们需要消除它的栈，并返回原来的状态，如何返回呢？通过保存ebp=100这个信息。所以我们返回ebp=100，esp=88。这也就是为什么要做上面这三个步骤。然后继续，movl $8,(%esp) ，将数值8放在esp所指向的位置。
接下来进入被调用函数f，利用到call指令，这里讲一下call指令的作用。常见的CPU的CALL指令（“调用”指令）的功能，就是以下两点：
(1)将下一条指令的所在地址（即当时程序计数器PC的内容）入栈
(2)将子程序的地址送入PC（即开始执行子程序）
这时候会将EIP寄存器压入栈（EIP用来存储CPU要读取指令的地址）， eip指向的是call的下一条指令,，addl $1, %eax（eax是X86汇编语言上cpu通用的寄存器名称，是32位寄存器，用来暂时存储数值或地址），随后进入函数并执行头三行：
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl 8(%ebp) , %eax
movl %eax , (%esp)
call g
继续看调用函数f的代码，第一行表示将ebp+8地址所在位置的值放入eax中，而由图解可知ebp+8的值实际上是8。这儿的8又正好是C语言里f(int x)的参数传递。所以，在32位X86的情况下，函数的参数传递是通过栈来实现的。我们在用call命令调用函数之前，先把需要的参数压入栈，然后再使用call命令将eip压栈，然后进入新的函数后，旧的ebp压栈，新的ebp指向的位置存了这个刚压栈的旧的ebp，所以我们可以通过新的ebp指向的位置，通过计算得到函数需要的参数值。接下来，movl %eax, (%esp) ，会把eax的值放入esp所指向的内存的位置，然后调用 g函数,，又可以压入call指令的下一条指令的地址。
进行g函数，执行前两条指令，得到的结果如下：
被调用函数g的第三条指令，movl 8(%ebp), %eax ，与之前的代码一致，将ebp+8位置的值存储在eax中。第四条指令，将eax+3，此时eax = 11。第五条指令，popl %ebp，将栈顶的那个数取出并存入到ebp寄存器中，ebp变成了72，因为这个时候esp执行的位置存放的值就是72，而这个值也是上一个函数中ebp的值。所以得到下图：
然后ret执行，ret执行时会把栈顶元素弹到eip中，即把在这里leave的地址弹到eip中，就可以执行leave 指令了，得到的图是：
leave 指令类似一条宏指令, 等价于movl %ebp, %esp popl %ebp。由已知，ebp=72中存取的值是84，这又是上一个的旧ebp的值，所以继续leave，弹出，得到下图：
这一步后，又遇到了一次ret，开始执行addl $1,%eax，由于之前的eax=11，所以现在变成了12。然后又碰到了leave指令，弹出，达到清栈的目的。效果图如下：
于是栈恢复了状态。此时main中2还剩下一条ret指令，由于之前一开始我们没考虑过main的地址压栈，所这部分问题留给操作系统。
总结：
一个函数的执行过程，会有自己的一段从ebp 到esp的栈空间。对于一个函数，ebp指向的位置的值是调用这个函数的上一个函数的栈空间的ebp的值， 这种机制使得leave指令可以清空一个函数的栈、达到调用之前的状态。由于在这个栈设置之前，有一个eip压栈的过程，所以leave 以后的ret正好对应了上一个函数的返回地址，也就是返回上一个函数时要执行的指令的地址，另外，由于对于一个函数的栈空间来说，ebp指向的位置存了上一个ebp的值， 再往上是上一个函数的返回地址，再往上是上一个函数压栈传参数的值，所以我们知道了自己的当前ebp，就可以通过栈的机制来获得参数。