递归的可视化（Fibonacci）

递归的可视化

修改递归函数，使其能够显示打印出每次函数递归调用的形参的值。

每一级调用的输出都带有一级缩进，就是使得程序的输出清晰、有趣并且有含义。

思路

以斐波那契数列为例，假设n=5,递归的形参如下：

 1------------------- 5
 2-----------------/     \
 3---------------4        3
 4-------------/   \     /  \
 5-----------3      2   2     1
 6---------/   \    
 7--------2     1

效果图如下：

代码实现

#include<stdio.h>
#include<stdlib.h>
#define MAX 50

long Fibonacci(long num);
void push(int i);
int pop(void);/*堆栈*/
int stack[MAX];/*栈顶*/ 
int tos = 0;

/*主函数*/
int main()
{
    int seriesSize = 0;/*数列的长度*/
    printf("此函数将生成Fibonacci数列\n");
    printf("请输入希望生成的数列的项数：");
    scanf("%d", &seriesSize);

    printf("\nFibonacci数列的第%d项是：%d", seriesSize, Fibonacci(seriesSize));
    printf("\n");

    return 0;
}/*end miain*/

/*计算Fibonacci数列的第n项*/
long Fibonacci(long num)
{
    static int d = 0;
    if (d == 0)
        push(0);

    d++;
    for (int i = 0; i < 6 * d; i++)
        printf(" ");
    printf("第%d层递归调用：形参num=%ld\n", d, num);
    if (num == 0 || num == 1)
    {
        d = pop();
        return 1;
    }
    else
    {
        push(d);
        return(Fibonacci(num - 1) + Fibonacci(num - 2));
    }
}

/*函数push:入栈函数*/
void push(int i)
{
    if (tos >= MAX)
    {
        printf("Stack Full\n");
    }
    stack[tos] = i;
    tos++;
}

/*函数pop:出栈函数*/
int pop(void)
{
    tos--;
    if (tos < 0)
    {
        printf("Stack Underflow\n");
        return 0;
    }
    return stack[tos];
}