递归

递归（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函数在计算时调用了自身。