{%hackmd @RintarouTW/About %}

# Recursion

## Many Faces of Recusion

### Binomial Coefficients with Recursive Definition

:::info
$$
\cases{n,k\in \mathbb{P}, n\geq k\geq 0\\
\binom{n}{0}=1\\
\binom{n}{n}=1\\
}\\
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\\
\begin{array}l
\ n\ 個選擇中選\ k\ 個 &= 首位不選時的可能 + 首位必選時的可能\\
&= n-1\ 個中選\ k\ 個(首位不選) + n-1\ 中選\ k-1\ 個 (首位必選)
\end{array}
$$

:::

### Polynomial Expression and Evaluation(Telescoping Form)

:::info
**Telescoping Form**/**Horner’s method**
$$
\begin{array}l
f(n)&=4n^3+2n^2-8n+9\\
&= (((4n+2)n-8)n+9
\end{array}
$$
:::

### Recursive Search
ex: Binary Search

### Recursively Defined Sequence

- Geometric Growth Sequence
$$
\cases{
B_0 = 100\\
B_k = 1.08B_{k-1}, k\geq 0
}
$$
- Fibonacci Sequence
$$
\cases{
F_0=1\\
F_1=1\\
F_k=F_{k-1} + F_{k-2}, k\geq 2
}
$$

TODO: Page 144

###### tags: `math`