第64章 递归函数
案例题目:递归函数——阶乘与斐波那契数列
本案例通过两个经典数学问题,演示TypeScript中递归函数的定义、调用及边界条件控制。阶乘强调“递减递归”,斐波那契数列强调“多分支递归”,两者共同展示递归的三要素:终止条件、递归调用、问题规模缩小。
设计思路
定义两个纯函数:factorial(n)计算n的阶乘(n≥0),使用if判断基线条件;fibonacci(n)返回第n个斐波那契数(n≥1),基线为n=1或n=2时返回1。调用时传入不同数值验证结果,并打印过程信息以观察递归顺序。
核心代码
// 阶乘:n! = n * (n-1) * ... * 1
function factorial(n: number): number {
if (n <= 1) return 1; // 基线条件:0! = 1! = 1
return n * factorial(n - 1); // 递归:缩小问题规模
}
// 斐波那契:F(n) = F(n-1) + F(n-2),F(1)=F(2)=1
function fibonacci(n: number): number {
if (n <= 2) return 1; // 基线条件
return fibonacci(n - 1) + fibonacci(n - 2); // 多分支递归
}
// 验证输出
console.log("5! =", factorial(5)); // 120
console.log("8! =", factorial(8)); // 40320
console.log("fib(5) =", fibonacci(5)); // 5
console.log("fib(10) =", fibonacci(10)); // 55
运行结果与验证方法
运行命令:ts-node recursion.ts 或 npx ts-node recursion.ts(需安装ts-node)。预期输出:
5! = 120、8! = 40320、fib(5) = 5、fib(10) = 55。可自行修改参数验证边界值(如 factorial(0) 应返回1)。
注意事项
递归必须有明确的基线条件,否则会栈溢出(RangeError)。Fibonacci递归存在大量重复计算,n>40时性能急剧下降;实际开发中建议用循环或记忆化优化。TypeScript需指定参数和返回值类型,此处均返回number。
成功要点:掌握“先写基线,再写递归”的编写顺序;学会用if控制递归终止;理解每次调用都创建独立栈帧,递归深度受JS引擎栈大小限制(通常约1万层)。此案例完整覆盖递归核心思想,为后续树、图等结构打下基础。