数学における漸化式（ぜんかしき、英: recurrence relation; 再帰関係式）は、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式である。

ある種の漸化式はしばしば差分方程式 (difference equation) と呼ばれる。また、「差分方程式」という言葉を単に「漸化式」と同義なものとして扱うことも多い。

漸化式の例として、ロジスティック写像 x n + 1 = r x n ( 1 − x n ) {\displaystyle x_{n+1}=rx_{n}(1-x_{n})}

が挙げられる。このような単純な形の漸化式が、しばしば非常に複雑な（カオス的な）挙動を示すことがあり、このような現象についての研究は非線型解析学などと呼ばれる分野を形成している。

漸化式を解くとは、 添字 n に関する非再帰的な函数として、一般項を表す閉じた形（英語版）の式を得ることをいう。
簡単な例

フィボナッチ数列は線型漸化式 F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

に初期値、 F 0 := 0 ,   F 1 := 1 {\displaystyle F_{0}:=0,\ F_{1}:=1} を与えて得られる。

この漸化式は、陽に書けば F 2 = F 1 + F 0 ,   F 3 = F 2 + F 1 ,   F 4 = F 3 + F 2 , … {\displaystyle F_{2}=F_{1}+F_{0},\ F_{3}=F_{2}+F_{1},\ F_{4}=F_{3}+F_{2},\dots } といった無限個の式と同じである。

こうして得られるフィボナッチ数列のはじめのほうを書けば0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

となる。後述するような方法で漸化式を解けば、特性多項式（固有多項式） t2 - t - 1 の二つの根を用いた閉じた式（英語版）が得られる。フィボナッチ数列の母関数は t 1 − t − t 2 {\displaystyle {\frac {t}{1-t-t^{2}}}}

という有理式である。
構造
定数係数斉次線型漸化式

定数係数の d-階斉次線型漸化式は、一般に a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}}

の形に表される式で、d 個の係数 ci はすべての i について定数となるものである。

一般にd-階斉次線型漸化式の解は、異なる公比をもつ d-個の幾何数列の和として表される。例外は、それらの幾何数列の公比を与える方程式の根が重根を持つ場合である[1]。このように幾何数列の和として書かれた式をビネーの公式 (Binet's formula) という[2]（ただし「ビネーの公式」という名称は、フィボナッチ数列の一般項を二つの冪数列の和として表す式の意味で用いられることのほうが多い）。

もう少し詳しく言えば、この線型漸化式は各 n (> d − 1) に対する無限本の線型方程式に関する連立方程式であり、この形の漸化式を満たす列は線型回帰数列 (linear recursive sequence) と呼ばれ、あるいは短く "LRS" とも呼ばれる。d-階の線型再帰列は初期値 a0, ..., ad−1 を任意に選ぶ分だけの自由度 d を持ち、それら初期値に対して一意に決定される。

この形の線型漸化式と同じ係数を持つ、漸化式の固有多項式または特性多項式 (characteristic polynomial) あるいは補助多項式 (auxiliary polynomial) と呼ばれる多項式 p ( t ) := t d − c 1 t d − 1 − c 2 t d − 2 − ⋯ − c d {\displaystyle p(t):=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}

は、その d 個の根が漸化式を満たす数列を求め、理解するのにきわめて重要な役割を果たす。
有理母関数

線型再帰列は、その母函数が有理函数となるような数列として特徴付けられる。母函数の分母は（適当な変換をうける違いを除いて）特性多項式であり、分子は初期値から決まる。

もっとも単純なものは、an = an−d なる周期数列 a0, a1, ..., ad−1, a0, a1, ... の場合であり、この列の母函数は幾何数列の和 a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 1 − x d = ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) + ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) x d + ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) x 2 d + ⋯ {\displaystyle {\begin{aligned}&{\frac {a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}}{1-x^{d}}}\\[9pt]&=\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{d}\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{2d}+\cdots \end{aligned}}}

として表される。もっと一般に、漸化式 a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}}

と母函数 a 0 + a 1 x 1 + a 2 x 2 + ⋯ {\displaystyle a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots }

が与えられたとき、多項式 1 − c 1 x 1 − c 2 x 2 − ⋯ − c d x d {\displaystyle 1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}

を使って、母函数級数の ad 以降の係数を消去することができる。つまり、母函数に先の多項式を掛け合わせれば b n := a n − c 1 a n − 1 − c 2 a n − 2 − ⋯ − c d a n − d {\displaystyle b_{n}:=a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}-\cdots -c_{d}a_{n-d}}