Introducción

La recursividad, junto a la iteración, son los dos mecanismos que suministran los lenguajes de programación para describir cálculos que, con pequeñas variaciones, han de repetirse un cierto número de veces.

¿Qué es la recursividad?

Es una característica de la mayoría de los lenguajes de programación, por la cual se permite que un procedimiento, o función, haga referencia a sí mismo dentro de su definición.

El concepto de recursividad no es nuevo. En el campo de las matemáticas podemos encontrar muchos ejemplos relacionados con él.

En primer lugar muchas definiciones matemáticas se realizan en términos de sí mismas. Considérese el clásico ejemplo de la función factorial:

donde la definición se realiza por un lado para un caso que denominamos base (n=0) y por otro, para un caso general (n>0) cuya formulación es claramente recursiva.

La propia definición recursiva del factorial de un número o las de tipos de datos como árboles y listas son ejemplos de recursividad.

Consideremos por otro lado las demostraciones por inducción (estrechamente relacionadas con las definiciones recursivas) que generalmente sólo necesita realizar una simple demostración para un caso base y una segunda para un caso general de tamaño n (con la ventaja de suponerlo demostrado para cualquier caso menor que n) de forma que queda demostrado para todos los casos.

De forma similar, cuando diseñamos una función recursiva podemos suponer que está resuelta para un tamaño menor.

De esta forma, la recursividad constituye una de las herramientas más potentes en programación.

La recursividad tiene la misma potencia expresiva que la iteración, en el sentido de que permite describir los mismos cómputos y las mismas funciones que pueden describirse mediante algoritmos iterativos.

El uso de la recursividad genera algoritmos más compactos que sus correspondientes versiones iterativas.

En este tema vamos a presentar la recursividad como una herramienta fundamental para el diseño de algoritmos y para el razonamiento formal sobre su corrección.

Veremos que el esfuerzo de razonamiento es menor pensando en recursivo que en iterativo.

Veremos también como estos algoritmos recursivos pueden ser transformados a su versión iterativa sin merma de corrección ni de eficiencia, normalmente con ganancia en esta última.

Resolver un problema P sobre unos datos D

¿ problema P datos D ?

Calcular la potencia n-ésima de a, siendo a y n enteros y a≥0 y n≥0

Q $\equiv$ { a ≥ 0 $\wedge$ n ≥ 0 }

Función POTENCIA (a:entero, n:entero) retorna (p:entero)

Planteamiento ITERATIVO al diseñar la solución

Calcular la potencia n-ésima de a, siendo a y n enteros y a≥0 y n≥0

$Q(x) \equiv a \geq0 \wedge n \geq0$

Función POTENCIA (a:entero, n:entero) retorna (p : entero) 
    var x : entero fvar
    x = 1
    para i = 1 hasta n hacer /* se repite un número n de veces */
        x = a * x /* problema p = multiplicar dos números */
    fpara 
    retorna x
ffunción

Planteamiento RECURSIVO al diseñar la solución

El mismo razonamiento que conduce a resolver el problema P sobre los datos D a partir del problema P sobre los datos D´ se aplica a su vez para resolver el problema P sobre los datos D’ a partir del problema P sobre los datos D’’, los cuales son aún más pequeños.

Se forma así, una sucesión D > D’ > D’’ > ... > Dt de datos cada vez más pequeños.

$Q(x) \equiv a \geq0 \wedge n \geq0$

Función POTENCIA (a:entero, n:entero) retorna (p:entero)

¿Cómo podemos calcular POTENCIA(a,n) a partir de POTENCIA(a,n-1)?

o, dicho de otra forma,

¿Cómo podemos calcular $a^{n}$partir de $a^{n-1}$?

$a^{n-1} = a^{n-1}*a$

POTENCIA(a,n) = POTENCIA(a,n-1) * a

$Q(x) \equiv a \geq0 \wedge n \geq0$

Función POTENCIA (a:entero, n:entero) retorna (p:entero)
    si n = 0 entonces retorna 1
    sino retornaPOTENCIA(a, n-1) * a
fsi ffunción