読み方：ぜんかしき

漸化式【recurrence relation】

概要

漸化式とは、数列のある項の値を、それより前の項を用いて表した式のこと。最初の項（初項）の値と漸化式が決まれば、そこから順番に後続の項の値を計算できる。数学の分野で定義された概念だが、コンピュータの計算手順を記述する際にも用いられる。

例えば、初項を2とし、次の項は現在の項に3を加えると定める場合、漸化式は a_n+1=a_n+3 となる。この式に従うと、2、5、8、11…という数列が順に得られる。漸化式は直前の一項だけでなく、複数の前の項との関係を表すこともある。

代表的な例がフィボナッチ数列である。初項と第2項を共に1とし、ある項をその直前の2項の和と定めると、1、1、2、3、5、8、13…という数列が得られる。等差数列や等比数列も、前の項に一定の数を足す、あるいは掛けるという規則を式にしたものであり、漸化式によって記述することができる。

漸化式で表された数列は、そのままではnを用いてaを直接求めることができないため、式を変形してnだけで表される一般項を導く作業が行われる。等差数列や等比数列は比較的容易に一般項へ変形できる一方、複雑な漸化式では置き換えや特性方程式、行列、母関数などの手法が必要になることがある。

再帰と漸化式

情報科学の分野において、漸化式は「再帰呼び出し」という処理の実装と強く結び付いている。プログラムの関数が自分自身を呼び出し、引数の値を少しずつ変えながら計算を進める再帰手法は、漸化式の構造をコードとして表現することができる。過去の計算結果を記憶して再利用し、計算量を削減する動的計画法などの手法も、計算対象を漸化式によって定式化することを前提に構築されている。

漸化式を用いて数値を求める考え方は古代の数学にまで遡る。複雑な現象や連続する変化を一挙に解くのではなく、直前の状態との関係という単純な規則の繰り返しに分解して捉える発想が根本にある。この考え方は、微分方程式の数値解法や、物理現象の変化をコンピュータ上で再現するシミュレーションの基礎理論にも通じている。

(2026.8.29更新)