fórmulas recursivas

Question

Estoy estudiando álgebra lineal. No sé cómo tratar las fórmulas recursivas, por ejemplo

• fibonacci
• cuando se debe encontrar un gran determinante del tamaño $n$ (Creo que Vandermonde utiliza una fórmula recursiva se encuentra allí, ¿o es inducción?)
• ¿cómo se pasa de una fórmula recursiva a una explícita?

Es una mala pregunta, pero necesito que me orienten.

Answer 1

(Desde una perspectiva un poco informática)

Una fórmula recursiva tiene dos partes: una condición terminal y una llamada recursiva.

Por ejemplo, digamos los números de Fibonacci. Digamos que $f(n)$ calculará el $n$ -ésimo número de Fibonacci. Nuestro dominio son los números naturales.

Por tanto, la función es a trozos:

$$f(n) = \begin{cases} 1, & \text{if }n\text{ = 1 or $n$ = 2} \\ f(n-1) + f(n-2), & \text{if }n\text{ > 2} \end{cases}$$

La condición terminal es cuando $n = 1$ o $n=2$ . En cualquier caso, la función devuelve un valor duro.

La llamada recursiva es la otra parte. Estamos definiendo la función (para ciertos valores) en términos de sí mismo . Si $n$ es lo suficientemente grande, esto provocará más llamadas recursivas. Finalmente, una de las llamadas recursivas será a $n=1$ o $n = 2$ por lo que devolverá un valor duro. Y luego la llamada recursiva que hizo que llamada recursiva tiene un valor duro, y así sucesivamente.

He aquí un ejemplo con $n =5$ : $$\begin{align} f(5) = f(3) + f(4)\\ = f(2) + f(3) + f(2) + f(1)\\ = 1 + f(1) + f(2) + 1 + 1\\ = 1+1+1+1+1\\ =\boxed{5}\\ \end{align}$$

Además, se podría tener una fórmula recursiva para el determinante de un $n \times n$ matriz. Piensa en cuál sería la condición terminal: para qué valores de $n$ ¿conoces una forma sencilla de calcular el determinante? Sin duda, para $n=1$ y $n=2$ pero tal vez incluso $n=3$ ? Y luego piensa en cómo definir recursivamente el determinante de una matriz mayor a partir de los determinantes de matrices menores (pista: expansión cofactorial).

Sin embargo, una advertencia: Una fórmula recursiva para determinantes es muy ineficiente, y tomará extremadamente largos tiempos de cálculo (incluso por ordenador) para valores mayores de $n$ .

Answer 2

La función Fibonacci es la siguiente:

$F_{n}=F_{n-1}+F_{n-2}$

$F_{0}=1, F_{1}=1$

Normalmente, esto se considera una recurrencia homogénea de segundo orden. Para llegar a una solución general, hay que escribir el polinomio característico y obtener las raíces (en este caso, es la proporción áurea). Puedes encontrar una buena referencia en el libro de Ralph Grimaldi (capítulo 7 si no me equivoco).

Algorítmicamente, sólo tienes que hacer los cálculos. Lleva tiempo, ya que en realidad estás calculando unos cuantos números repetidas veces (es un ejemplo típico en temas como la Programación Dinámica).