递推公式

递推公式一步一步地构造数列，用前面已有的项来定义每一个新项——就像一份食谱说“要得到明天的值，就拿今天的值加上 3”。你一次只爬一级梯子。

这样的定义有两部分：一个或多个起始值（初始条件，例如 a_1 = 2）和一条用前面的项产生下一项的递推规则（例如 a_n = a_(n−1) + 3）。没有初始条件，规则就无从起步。

递推自然且容易写出，但有代价：要求第 100 项，你必须先算出前面的 99 项。而当显式公式存在时，它能让你直接跳到任意一项。著名的斐波那契数列 a_n = a_(n−1) + a_(n−2) 就是这样定义的。