栈与递归的实现：阶乘

一、问题引入

递归函数的实现与栈结构的关系，将公式以代码的方式体现出来。

最好的例子莫过于：阶乘

分别求：1~n 的阶乘

1!=1
2!=1*2
3!=1*2*3
4!=1*2*3*4

数学公式：

二、解决过程

递归函数就是不断的调用自身，但递归函数必须预留出口，否则陷于死循环。

代码部分

#include <stdio.h>

static long Fact(long n)
{
	if (0 == n)
		return 1;
	else
		return n * Fact(n-1);
}

int main(void)
{
	// 计算1~n的阶乘
	printf("\n");
	int n = 5;
	for (int i = 1; i <= n; i++)
	{
		long val = Fact(i);
		printf("%d的阶乘:%ld\n", i, val);
	}
	return 0;
}

• 时间复杂度：O(\(2^n\))

• 空间复杂度：O(\(n\))

三、反思总结

递归的优缺点分析：

• 优点：代码简洁，结构清晰，符合数学公式

• 缺点：递归需要入栈和出栈操作，入栈层次比较深，对于栈空间和效率产生很大的挑战。

四、参考引用

数据结构第二版：C语言版 【严蔚敏】 第3章 栈与队列