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.
Where it lands in Jayverse
- DeFi: set up compounding/reward-accrual formulas in jayverse-defi as explicit recurrences. Solve for at least the growth rate, not only a simulation, to catch compounding bugs before they show up as a wrong balance.
- Bridge: size the relayer's cross-chain confirmation backoff from the closed-form total-wait formula. Don't tune retry/backoff by trial and error when the exercise's three methods (memoized recursion, iteration, closed form) already give the number.
- OFA: write the recurrence for any nested or recursive auction step before implementing it. A solver step that calls itself (recursive matching, nested clearing) should have its asymptotic cost known from the recurrence ahead of time, the same discipline Merkle-proof aggregation needs.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| closed-form solution | 닫힌 형태의 해, 명시적 수식으로 바로 구할 수 있는 답 · 재귀식을 풀어 얻는 결과. "has a closed-form solution derivable from the roots" |
| read off | (수식·그래프에서) 값을 바로 읽어내다 · 방정식을 풀고 나서 계수를 뽑아낼 때. "read the coefficients back off to derive a closed form" |
| self-similar | 자기유사적인, 같은 패턴이 단계마다 반복되는 · 재귀적으로 구조가 반복되는 시스템을 가리킬 때. "For self-similar systems whose cost repeats at each level" |
| master theorem | 마스터 정리 · 분할정복 알고리즘의 점근적 비용을 직접 구하는 정리. "using the master theorem" |
| package X as Y | X를 Y의 형태로 담아내다, 표현하다 · 수열을 하나의 함수로 다룰 때. "packages a sequence as the coefficients of a... series" |
| set up (a recurrence) | (재귀식을) 세우다, 정식화하다 · 문제를 수식으로 정확히 표현하는 첫 단계. "the ability to set up the recurrence correctly" |
| derivable from | ~로부터 유도 가능한 · 근을 통해 답을 이끌어낼 수 있을 때. "a closed-form solution derivable from the roots" |
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/.