フィボナッチ数
しかし、上記例1のプログラムでは n が与えられてから Fn が求まるまでに F n ∝ φ n {\displaystyle F_{n}\propto \phi ^{n}} 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、例4に示すような指数関数的なコールを必要としない実装を行うか、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式(上記例3)や行列表現を利用して対数時間(英語版)での計算を行う。
T n = α n ( α − β ) ( α − γ ) ( α − δ ) + β n ( β − γ ) ( β − δ ) ( β − α ) + γ n ( γ − δ ) ( γ − α ) ( γ − β ) + δ n ( δ − α ) ( δ − β ) ( δ − γ ) {\displaystyle T_{n}={\frac {\alpha ^{n}}{(\alpha -\beta )(\alpha -\gamma )(\alpha -\delta )}}+{\frac {\beta ^{n}}{(\beta -\gamma )(\beta -\delta )(\beta -\alpha )}}+{\frac {\gamma ^{n}}{(\gamma -\delta )(\gamma -\alpha )(\gamma -\beta )}}+{\frac {\delta ^{n}}{(\delta -\alpha )(\delta -\beta )(\delta -\gamma )}}}
となる。