Recurrence Relations and Generating Functions TODO
Concept
A recurrence relation defines a sequence's terms in terms of earlier terms, and it's the most natural language for describing an algorithm's cost. A linear homogeneous recurrence with constant coefficients has a closed-form solution derivable from the roots of its characteristic equation, and when there's a nonhomogeneous term, you add a particular solution to build the general solution. A generating function packages a sequence as the coefficients of a formal power series, treating it as a single function; you turn the recurrence into an algebraic equation on that function, solve it, and read the coefficients back off to derive a closed form. Recurrences of the shape that comes out of divide-and-conquer algorithms can be solved directly for their asymptotic order using the master theorem, which tells you whether the recursive cost or the divide/combine cost dominates. What matters isn't always finding a closed form — it's the ability to set up the recurrence correctly and read off the growth rate from it.
Real work like algorithm complexity analysis, cumulative delay in retry backoff, and recursive estimates of queue length all starts from setting up a recurrence correctly.
Code & Formula
# 재귀관계와 생성함수(가볍게) — 피보나치 점화식을 (1) 메모이제이션 재귀, (2) 반복 계산,
# (3) 특성방정식 닫힌 형태(비네 공식)로 각각 구현해 세 방법의 결과가 일치하는지 확인.
from functools import lru_cache
import math
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2) # F(n) = F(n-1) + F(n-2)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def fib_closed(n):
# 특성방정식 x^2 = x + 1 의 근 phi, psi 로부터 얻는 닫힌 형태(비네 공식).
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2
return round((phi ** n - psi ** n) / math.sqrt(5))
print(" n | memo | iter | closed")
for n in range(0, 16):
m, i, c = fib_memo(n), fib_iter(n), fib_closed(n)
assert m == i == c, f"불일치 at n={n}: {m}, {i}, {c}"
print(f"{n:2} | {m:4} | {i:4} | {c:4}")
print("\n세 방법 모두 n=0..15 에서 일치.")
# 생성함수 관점: F(x) = x / (1 - x - x^2) 의 계수를 급수 전개로 뽑아 같은 수열이 나오는지 확인.
def fib_via_series(order):
coeffs = [0] * (order + 1)
coeffs[1] = 1 # 분자 x
# (1 - x - x^2) * F(x) = x => F[n] = F[n-1] + F[n-2] (n>=2), F[0]=0, F[1]=1
for k in range(2, order + 1):
coeffs[k] = coeffs[k - 1] + coeffs[k - 2]
return coeffs
series = fib_via_series(15)
print("생성함수 급수 전개로 얻은 F(0..15):", series)
Exercise
Pick a linear recurrence and implement it three ways — memoized recursion, iteration, and the characteristic-equation closed form — then compare results and running time for large n.
Practical Connection
For self-similar systems whose cost repeats at each level — Merkle tree verification cost, per-depth cost of recursive proof aggregation, total wait time under exponential backoff retries — setting up a recurrence relation is the most accurate way to work out the cost.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.