# Use of Recursively Defined Functions

Recursion is definitely fascinating and can generate sequences that would need lengthy functions.

While doing combinatorics, I found that certain counting problems and some probability computation naturally require recursion to solve them.

Could you elaborate other fields/problems except combinatorics where this is helpful? Or these recursive sequence appear as solution?

An example of counting problem involving recurrence relation is here:

No of n-digit numbers with no adjacent 1s.

Sorry if the tags are not appropriate. I appreciate any edition of it.

-
At a low level, reduction formulas for integrals. –  André Nicolas Dec 19 '12 at 22:41

The study of logic analyses recurrence on many levels. For instance, self-referential paradoxes are definitions of the same syntactic type as recurrence. In fact, the fact that f(x) = f(x) + 1 doesn't have a solution is very much the same reason as "this sentence is false". Tarski's undefinability of truth is a much deeper limit on the capability of recurrence in sufficiently strong formal systems.

Now, if you are looking for something with a little more concrete domains than syntaxes or truth values, there is always basic computer science with many functions defined by recurrence. There is the Ackermann function, the fast-growing hierarchy, and many other gems.

However, there is a really strong sense in which your question is poorly defined. All of these examples are in some sense combinatorial, and other examples like those in graph theory and higher data structures are naturally in the field. The liar paradox, for instance, can be seen as a particular combinatorial question on a tree with two nodes, and more widely, just as all mathematics can be seen interpreted as a sufficiently strong theory of arithmetic, the same goes for interpretations in combinatorics. So, although you can get examples from other fields, there is always going to be a sense where you can look at the example and find it's "just another combinatorial problem."

-
I do accept that I defined it narrowly. –  007resu Dec 19 '12 at 21:51
But, I appreciate how you connected logical paradoxes as special recurrences. –  007resu Dec 19 '12 at 21:59
1. Cox-De Boor recursion for cardinal $b$-splines $b_n=(\mathbb{1}_{[0,1]})^{\ast n}$: $$\begin{eqnarray} b_1 &=& \mathbb{1}_{[0,1]} \\ b_{n+1}(x) &=& \frac{x}{n} b_n(x) + \frac{n+1-x}{n} b_n(x - 1)\end{eqnarray}$$
2. Spline interpolation. This one's a bit technical but it is used to interpolate discrete signals (e.g. when zooming in on an image). Let $|\alpha| < 1$ and $g$, $g_+$, $g_-$ be discrete kernels $\mathbb{Z} \to \mathbb{R}$ defined by $$\begin{eqnarray} g_+(n) &=& \begin{cases} \alpha^{n} & n \geq 0 \\ 0 & n < 0\end{cases} \\ g_-(n) = g_+(-n) &=& \begin{cases} \alpha^{-n} & n \leq 0 \\ 0 & n > 0\end{cases} \\ g(n) = (g_+ \ast g_-)(n) &=& \frac{1}{1-\alpha^2}\sum_{k \in \mathbb{Z}} \alpha^{|k|}\end{eqnarray}$$ Then if $f {: \mathbb{Z} \to \mathbb{R}}$ is a discrete signal the convolution $f \ast g$ can be computed efficiently despite the infinite support of $g$. Note that $$f \ast g = f \ast (g_+ \ast g_-) = (f \ast g_+) \ast g_-$$ and convolutions with $g_{\pm}$ can be computed recursively: $$\begin{eqnarray} h(n) = (f \ast g_+)(n) &=& \sum_{k=0}^{\infty} f(n - k) g_+(k) &=& f(n) + \alpha\,(f \ast g_+)(n-1) \\ (h \ast g_-)(n) &=& \sum_{k=0}^{\infty} h(n + k) g_-(-k) &=& h(n) + \alpha\,(h \ast g_-)(n+1) \end{eqnarray}$$ (Convolution with $g_+$ is called a causal filter and with $g_-$ an anti-causal filter.)