Función recursiva

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de febrero de 2020; las comprobaciones requieren 4 ediciones .

Una función recursiva (del latín recursio - retorno) es una función numérica de un argumento numérico que se contiene a sí mismo en su notación. Esta notación permite calcular valores a partir de valores , de forma similar al razonamiento por inducción . Para que el cálculo se complete para cualquier , es necesario que para algunos la función se defina de forma no recursiva (por ejemplo, para ). $f(n)$ $f(n)$ $f(n-1),f(n-2),\ldots$ $norte$ $norte$ $n=0,1$

Ejemplos

Un ejemplo de una función recursiva que da el n-ésimo número de Fibonacci :

$F={\begin{casos}F(0)=0;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{casos}}$ [una]

Guiados por esta notación, podemos calcular para cualquier n natural en un número finito de pasos. Es cierto que, en el camino, deberá calcular adicionalmente los valores de . $F(n)$ $F(n-1),F(n-2),\ldots,F(2)$

Formulario cerrado

Debido a la sobrecarga, es útil saber si una función recursiva tiene una forma no recursiva (cerrada).

Es posible que no se encuentre una forma cerrada para todas las funciones recursivas (relaciones). Para algunos de ellos, solo se han encontrado formas cerradas aproximadas. Algunas relaciones recursivas, como el factorial , se consideran operaciones matemáticas elementales.

Por ejemplo, una función recursiva que describe la suma de números naturales:

$f={\begin{casos}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{casos))$

se puede traducir a forma cerrada: . $f={\frac{n(n+1)}{2}}$

Aplicaciones

Las funciones recursivas juegan un papel importante en la teoría de los algoritmos , ya que muchos algoritmos tienen una estructura recursiva.

Notas

↑ Fórmula recurrente // Wikipedia. — 2020-03-07. Archivado desde el original el 7 de junio de 2022. (Ruso)