递归

来自吾萌百科
镜华酱讨论 | 贡献2024年7月7日 (日) 15:31的版本 →‎例子:​ // Edit via Wikiplus
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

递归(Recursion)是指函数的定义中使用函数自身。

递归与递推的区别

一个实际问题的各种可能情况构成的集合通常称为“状态空间”。

以已知的“问题边界”为起点像“原问题”正向推导的扩展方式就是递推。

以原问题为起点尝试寻找把状态空间缩小到已知的“问题边界”的路线,再通过该路线反向回溯的便利方式就是递归。

例子

斐波那契数列

int fib(int n) {
	if (n < 1)
        return 0;
	if (n < 3)
		return 1;
	return fib(n - 1) + fib(n - 2);
}

在此例中,n>=3时,fib函数在计算时调用了自身。