Diferencia entre revisiones de «Recursión (ciencias de computación)»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 20:10 20 jun 2009

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva.

FUNCIÓN Factorial(n)
    SI (n<2) ENTONCES
        Factorial = 1;
    SINO
        Factorial = n * Factorial(n-1);
    FSI
FFUNCIÓN

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son:

Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Recursividad indirecta

Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y éstas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.

Subrutina_A → Subrutina_B → Subrutina_A
Subrutina_A → Subrutina_B → Subrutina_C → Subrutina_D → Subrutina_A

Véase también

Recursión

@@ Línea 1: / Línea 1: @@
 Un '''algoritmo recursivo''' es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva.
+<source lang=text>FUNCIÓN Factorial(n)
-Algunos ejemplos de [[recursión|recurrencia]]:
+    SI (n<2) ENTONCES
-*'''En un texto''':
+        Factorial = 1;
- Para saber qué es la recurrencia, primero hay que saber qué es la recurrencia.
+    SINO
-*'''En un acrónimo''':
+        Factorial = n * Factorial(n-1);
- ¿Qué es '''GNU'''? → '''G'''NU '''N'''o es '''U'''nix
+    FSI
- ¿Qué es '''PHP'''? → '''P'''HP: '''H'''ipertext '''P'''reprocessor
+FFUNCIÓN</source>
-*'''En [[matemáticas]]''':
- f(x) = x * f(x-1)
-*'''En un algoritmo''':
- FUNCIÓN Factorial(n)
-   INICIO
-     SI (n<2) ENTONCES
-       Factorial = 1;
-     SINO
-       Factorial = n * Factorial(n-1);
-     FIN-SI
-   FIN
 Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un '''caso base''' de la recursividad.