PDF de programación - Recursividad

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Recursividad

12 RECURSIVIDAD

12.1 NOCIONES GENERALES

La recursión o recursividad es una técnica de resolución de algunos problemas particulares. En general, decimos
que la definición de un concepto es recursiva si el concepto es definido en términos de sí mismo. Así, por ejemplo,
en matemática, se da el nombre de recursión a la técnica consistente en definir una función en términos de sí misma.
Un ejemplo bastante conocido de definición de una función recursiva es el de la función factorial (!), definida para
los enteros positivos:

! : ℕ0 fi
ℕ
! = ·

− 1! si > 0
1 si = 0



Existen múltiples ejemplos de definiciones recursivas. Otro ejemplo es la siguiente definición del conjunto de los

números naturales (ℕ):

a) 1 pertenece a ℕ.
b) Si n pertenece a ℕ, entonces n+1 pertenece a ℕ.

En toda definición recursiva distinguimos dos partes:

- Caso base o elemental. Existe uno o más casos (generalmente de menor tamaño) que pueden resolverse sin
recursión. Es decir, para uno o más casos se conoce la definición del concepto mismo, es decir, no se necesita
de la recursión para definirlo. Por ejemplo, en las funciones definidas recursivamente, para uno o más valores
del domino se conoce el valor que corresponde al rango (o codomino). Así, en el ejemplo de la función
factorial el caso base es 0! = 1.

- Una definición recursiva, circular o caso general. Decimos que la definición es circular porque se hace ‘en
términos de sí misma’, es decir, incorpora una o más aplicaciones de sí misma dentro de la definición. Por
ejemplo, en la función factorial, la definición circular corresponde a :

n! = n ·

(n-1)!, si n > 0

Así, n! queda definido en términos de (n-1)!, el cual a su vez está definido en términos de (n-2)! y así

sucesivamente hasta llegar a 0!, que es el caso base o valor del dominio conocido, en donde la recursión para.

En Computación, la recursión se encuentra presente en la definición de módulos (funciones, procedimientos,

subrutinas, etc.) recursivos así como en la definición de tipos de datos recursivos.

La mayor parte de los lenguajes de programación soportan la recursión permitiendo que un módulo pueda
invocarse a sí mismo. Por medio de la recursión, podemos de realizar repeticiones. Ya hemos visto cómo las
repeticiones en los lenguajes de programación imperativos, y en particular en el caso de C, las implementamos por
medio de sentencias de iteración. Veremos que también pueden hacerse empleando recursión.

12.2 MÓDULOS RECURSIVOS

En general, decimos que un módulo es recursivo cuando el módulo (función, procedimiento, subrutina, etc.) se
encuentra definido en términos de sí mismo. Es decir, un modulo es recursivo si (a) dentro de su cuerpo existe una
invocación a sí mismo, lo que correspondería al caso recursivo o general; (b) existe uno o varios casos elementales
que pueden resolverse directamente sin necesidad de recursión, que correspondería al o los casos bases.

U.N.S.L. Argentina

118

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Recursividad

Entonces, ¿por qué escribir módulos recursivos, cuando existen las iteraciones? En la mayoría de los casos, una
función recursiva se puede reemplazar por una función iterativa; sin embargo, muchas veces la solución recursiva
resulta más clara e intuitiva que la iterativa; además, permite en algunos casos, definir módulos complejos de
manera muy compacta. Por otro lado, hay que tener en cuenta que no debe recomendarse de forma indiscriminada el
uso de la recursión. El programador debe hacer un balance entre los beneficios de un módulo sencillo, escrito con
mayor facilidad, contra el tiempo adicional de ejecución así como la posibilidad de dificultades para encontrar y
corregir errores inherentes a una solución recursiva.

Como toda repetición, la recursión también puede ser finita o infinita, dependiendo de la condición que la
controla. La condición que controla la recursión es el casos base (o los casos base, si hay más de uno), que
permite(n) que la recursión “termine” o “pare”.

En la Figura 12.1 damos una definición de una función en C que calcula la factorial de un número entero n. En
la rama del falso existe, en el valor retornado por la función, una invocación recursiva (factorial(n – 1)).
Esta es la invocación que hace que factorial sea una función definida en forma circular. El caso base es n igual
a 0. Véase en el ejemplo que para n == 0 la función devuelve 1. La función factorial está, así, definida
recursivamente: tiene una definición circular y al menos un caso base o valor del dominio para el cual se conoce el
valor del rango que retorna la función.

long factorial(int n){
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}

Figura 12.1. Ejemplo de función recursiva en C.

Supongamos, ahora, que dicha función es invocada en un programa de la siguiente manera:

printf("%ld \n", factorial(2));

Puede verse en la Figura 12.2 que para factorial(2) se realizan tres llamadas de la función, antes que se
obtenga un valor para factorial(0)(caso base) y puedan entonces calcularse los valores correspondientes a las
llamadas anteriores que han quedado pendientes de resolver.

factorial(2)

2 * factorial(1)

1 * factorial(0)

1



Figura 12.2. Cálculo de factorial(2).

En efecto, en la primera llamada, siendo n igual a 2 (y en consecuencia mayor a cero), se invoca nuevamente
a factorial con el parámetro n–1, es decir, factorial(1); en el segundo llamado, siendo n igual a 1 (y
en consecuencia mayor a cero) se invoca nuevamente a factorial con el valor n – 1 (cero), y es entonces, en

U.N.S.L. Argentina

119

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Recursividad

el tercer llamado, que siendo n igual a 0, la función factorial retorna 1, pudiendo ahora calcularse, yendo
hacia atrás, los distintos valores de las expresiones pendientes no resueltas.

Este mecanismo, que el compilador se encarga de implementar, implica dejar pendiente el cálculo de la función
hasta tanto se obtenga un valor conocido para la función. En el caso de la función factorial esto ocurre cuando
n es igual a 0, donde factorial(0) devuelve el valor 1.

12.3 RECURSIVIDAD. EJEMPLOS

Veamos algunos otros ejemplos de definiciones recursivas que contemplen otros aspectos de la recursión tales
como el hecho de que en la definición pueda haber más de una invocación recursiva, tal como sucede con la
definición de la función que calcula el número de Fibonacci.

SUCESIÓN DE FIBONACCI

Fibonacci, o más correctamente Leonardo de Pisa o Leonardo Pisano, nació en Pisa, Italia, alrededor de 1175.
Hijo de Guglielmo Bonacci, comenzó –quizás– a usar el nombre Fibonacci como una abreviatura de “filius
Bonacci”, hijo de Bonacci. Debido a que su padre tenía contactos comerciales con el norte de África, Fibonacci
creció con una educación influenciada por la cultura de los moros, especialmente su matemática. Estos a su vez
habían sido influenciados por la cultura hindú que utilizaban la notación posicional decimal (empleada hoy en día)
con los símbolos arábigos, especialmente el cero. Fibonacci introdujo esta matemática, incluida la forma, o
algoritmos, de realizar las operaciones elementales, en la Europa de esa época, que todavía utilizaba el sistema
romano de numeración.

En su libro “Liber abbaci” (Libro del Ábaco o Libro del Cálculo), no solo introdujo el sistema hindú–arábigo de
numeración y cálculo, sino también el problema de los conejos como una forma de los lectores del libro de practicar
las operaciones introducidas. Este problema puede resumirse así:

“Si una pareja de conejos son puestos en un campo, y si los conejos toman un mes en madurar, y si luego
producen una nueva pareja de conejos cada mes a partir de ese momento, ¿cuántas parejas de conejos habrá en doce
meses?”

Se supone que los conejos no mueren ni se escapan. Este problema dio origen a la sucesión de números: 0, 1, 1,

2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Así los términos de la sucesión pueden verse como:

término

f11
valor 0 1 1 2 3 5 8 13 21 34 55 89

f10

f2

f3

f9

f4

f5

f6

f0

f1

f7

f8

...
...



Figura 12. 3. Sucesión de Fibonacci

El matemático francés Edouard Lucas (1842-1891), le dio el nombre de números de Fibonacci a esta sucesión,

además de descubrir importantes propiedades de la misma.

Cada término de la sucesión se calcula sumando los dos anteriores, salvo los dos primeros, que son 0 y 1
respectivamente. Es decir, cualquier término fn de esta sucesión puede calcularse por medio de una definición
recursiva:

f0 = 0

f1 = 1



El primer término de la sucesión es el 0 (caso base).

El segundo término de la sucesión es el 1 (caso base).

fn = fn–1 + fn–2

El tercer término y los sucesivos se calculan recursivamente.

U.N.S.L. Argentina

120

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Recursividad

Obsérvese que esta definición recursiva, en la parte de la definición circular o caso general, la función queda
definida en término de dos aplicaciones recursivas de la función, en lugar de una como ocurría, por ejemplo, con la
definición de la función factorial. La definición cuenta, además, con dos casos base o elementales: el valo