Uso de funciones definidas recursivamente

El estudio de la lógica analiza la recurrencia en muchos niveles. Por ejemplo, las paradojas autorreferenciales son definiciones del mismo tipo sintáctico que la recurrencia. De hecho, el hecho de que f(x) = f(x) + 1 no tenga solución es en gran medida la misma razón que "esta oración es falsa". La indefinibilidad de la verdad de Tarski es un límite mucho más profundo a la capacidad de recurrencia en sistemas formales suficientemente fuertes.

Ahora, si está buscando algo con dominios un poco más concretos que la sintaxis o los valores de verdad, siempre hay informática básica con muchas funciones definidas por recurrencia. Está la función de Ackermann, la jerarquía de rápido crecimiento y muchas otras gemas.

Sin embargo, hay un sentido muy fuerte en el que su pregunta está mal definida. Todos estos ejemplos son, en cierto sentido, combinatorios, y otros ejemplos como los de la teoría de grafos y estructuras de datos superiores están naturalmente en el campo. La paradoja del mentiroso, por ejemplo, puede verse como una pregunta combinatoria particular en un árbol con dos nodos, y más ampliamente, así como todas las matemáticas pueden verse interpretadas como una teoría suficientemente fuerte de la aritmética, lo mismo ocurre con las interpretaciones en combinatoria. Entonces, aunque puede obtener ejemplos de otros campos, siempre habrá un sentido en el que puede mirar el ejemplo y encontrar que es "solo otro problema combinatorio".

Dos ejemplos de procesamiento de señales que apliqué recientemente.

1. Recurrencia de Cox-De Boor para cardenal$b$-estrías$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. Interpolación de splines. Este es un poco técnico, pero se usa para interpolar señales discretas (por ejemplo, al hacer zoom en una imagen). Dejar$|\alpha| < 1$y$g$,$g_+$,$g_-$ser núcleos discretos$\mathbb{Z} \to \mathbb{R}$definido por $$\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}$$ Entonces sí$f {: \mathbb{Z} \to \mathbb{R}}$es una señal discreta la convolución$f \ast g$se puede calcular de manera eficiente a pesar del soporte infinito de$g$. Tenga en cuenta que $$f \ast g = f \ast (g_+ \ast g_-) = (f \ast g_+) \ast g_-$$ y circunvoluciones con$g_{\pm}$se puede calcular recursivamente: $$\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}$$ (Convolución con$g_+$se llama filtro causal y con$g_-$un filtro anti-causal.)

El análisis de algoritmos está lleno de relaciones de recurrencia.