递归执行顺序探究-斐波那契数列为例 原创

都说递归使用起来比较简单，但是递归执行的顺序是什么样的？我们来探究一下，以斐波那契数列为例

使用C语言

复制收展Cpp#include <stdio.h>
//斐波那契数列 1,1,2,3,5,8...

//返回第几个元素 
int Fibonacci(int n){  
	printf(">>>>>>>>>n=%d\n", n);
	if(n==1 || n==2) {
		printf("************************%d 递归返回return 1\n",n);
		return 1;
	}
	printf("1---\n");
	//递归语句A 
	int a = Fibonacci(n-1);
	printf("2======\n");
	//递归语句B 
    int b = Fibonacci(n-2);
    printf("3+++++++++\n");
    //其他语句C 
    int c = a+b;
    printf("c=a+b=> %d=%d+%d\n",c,a,b);
    printf("4###\n");
    return c;
	//return Fibonacci(n-1)+Fibonacci(n-2);
}

int main()
{int n=6;
	printf("需要求斐波那契数列第几个元素=");
	scanf("%d", &n); 
	printf("斐波那契数列第 %d 个元素是 %d\n",n, Fibonacci(n));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

输出拿出来编号

换种画法，执行顺序其实是这样的，看的比较清晰。

当遇到递归语句A执行， 必须有返回值，才继续进行下面语句；  所有当Fibonacci(2)=1才接着执行之后的语句；

1、Fibonacci(5) 函数调用

遇到递归语句A

2、Fibonacci(5-1)

3、Fibonacci(4-1)

操作数栈A对于 4、3依次入栈（没有返回值的）；

4、Fibonacci(3-1)=1

n=2有返回值，返回；

栈顶n=3进行操作

5、Fibonacci(3-2)=1

有返回值，3出栈

6、此时操作数栈B有两个操作数了，两个数操作,两个数出栈，得到的和也就是F(3)=2入栈;

栈顶n=4进行操作

7、Fibonacci(4-2)=1

有返回值，4出栈，此时递归语句A执行完成，且返回值为F(4)=3赋值给a.

=============

9、执行递归语句B

10、Fibonacci(5-2)

操作数栈A对于3入栈（没有返回值的）；

11、Fibonacci(3-1)=1

有返回值，执行之后的语句

栈顶n=3进行操作

12、Fibonacci(3-2)=1

有返回值，3出栈，此时递归语句B执行完成，且返回值为F(3)=2赋值给b.
计算a+b后函数返回。

上图执行顺序看的比较清晰，可程序执行怎么实现的 ？

可以使用两个栈，栈A存放没有返回值的n，栈B存放函数返回值。