函数递归调用？看这文就够了( 二 ) _递归

文章插图
执行完call B，就开始在模块B中执行，一直执行到ret返回指令，此时函数调用栈区示意图如下（左边为返回后，右边为返回前）。

文章插图
执行完ret返回指令，将栈顶元素出栈送给程序计数器PC以供CPU继续执行主模块A中的剩余指令。
实际上，函数调用时入栈保护的不仅仅有主模块中调用指令之后的指令的地址，还有一些变量或者说数据，每个函数都有每个函数的局部变量，在主函数中调用子函数，主函数中的局部变量必须入栈保护，否则就会丢失。比如下面这个例子：

int add(int x,int y){int a=x+1;int b=y+1;int c=a+b;return c;}int main{int a=1,b=2;int c=add(a,b);printf(“%d+%d=%d ”,a,b,c);return 0;}

主函数和add函数里都有变量a和b，执行完add函数再返回到主函数中a的值必须还为1，b的值必须还为2，因此可以在调用add函数前先将主函数的所有变量（a和b）入栈保护，待执行完返回主函数时再出栈送给变量a和变量b 。
递归函数的调用
递归函数的调用本质上也是函数的调用，只不过是自己在调用自己罢了。
以求斐波那契数列的项为例：

int fibonacci(int n){if(n==1||n==2) //假设本条指令的地址为10000return 1; //假设本条指令的地址为10001int a=fibonacci(n-2); //假设本条指令的地址为10002int b=fibonacci(n-1); //假设本条指令的地址为10003int c=a+b; //假设本条指令的地址为10004return c; //假设本条指令的地址为10005}

如果进入函数的n是1或者是2，那么就直接返回1；
否则，就继续递归下去。
假设主函数调用斐波那契函数的指令的地址为15000，其下一条指令的地址为15001 。
假设我们要求斐波那契数列的第5项，公式为
f(5)=f(3)+f(4)=[f(1)+f(2)]+[f(2)+f(3)]=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]函数调用栈的示意图如下。
第一步，从主函数中进入斐波那契函数，传入的n为5 。
第二步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=5，将n=5压入数据栈，传入的n=3 。

文章插图
第三步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=3，将n=3压入数据栈，传入的n=1 。

文章插图

文章插图
第四步，此时n=1，可以直接返回1给上层的斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=3给上一层斐波那契函数的n，回到上层的斐波那契函数。

文章插图
第五步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，也就是将10004入栈，此时n=3，将n=3压入数据栈，此时a=1，将a=1压入数据栈，传入的n=2 。

文章插图

文章插图
第六步，此时n=2，可以直接返回1给上层斐波那契函数的b，返回的同时出栈10004给程序计数器PC，出栈n=3给上一层斐波那契函数的n，出栈a=1给上一层斐波那契函数的a，回到了上层的斐波那契函数。

文章插图
第七步，执行程序计数器PC指向的指令（内存地址为10004的指令），也就是执行int c=a+b，然后顺序执行一直到返回，返回2给上一层斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=5给上一层的斐波那契函数的n，回到上层的斐波那契函数。
f(5)=f(3)+f(4)=[f(1)+f(2)]+[f(2)+f(3)]=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]此时红色部分已通过递归计算完成。
第八步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，也就是将10004入栈，此时n=5，将n=5压入数据栈，此时a=2，将a=2压入数据栈，传入的n=4 。
第九步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=4，将n=4压入数据栈，传入的n=2 。