Recursividad

Tema 11. Diseño de algoritmos recursivos

1

Apuntes para la asignatura

Informática
Facultad de Ciencias (Matemáticas)
Departamento de Lenguajes y
Ciencias de la Computación

http://www.lcc.uma.es/personal/pepeg/mates

UNIVERSIDAD DE MÁLAGA

Tema 11. Diseño de algoritmos recursivos
11.1. Recursión................................................................ .........................................2
11.1.1 Verificación de los subprogramas recursivos............................................... 3
11.2 Recursividad frente a iteración................................................................ ..........4
11.3 Eficiencia de los algoritmos recursivos ............................................................. 5
11.3.1 Sobrecarga debida al funcionamiento interno.............................................5
11.3.2 Sobrecarga debida a la solución recursiva .................................................. 6
11.3.3 Iteración o recursión................................................................ .................... 7
11.4 Ejemplos clásicos de recursividad ................................................................ ....8
11.4.1 Las torres deHanoi................................................................ ..................... 8
11.4.2 Algoritmos de búsqueda recursivos .......................................................... 11
11.4.2.1 Búsqueda lineal recursiva................................................................ ....11
11.4.2.2 Búsqueda binaria recursiva ................................................................ .12

Bibliografía• Programming with TopSpeed Modula-2. Barry Cornelius. Addison-Wesley.
• Pascal y estructuras de datos. Nell Dale y Susan C. Lilly. McGraw-Hill.
• Fundamentos de programación. L. Joyanes. McGraw-Hill.

2

11.1. Recursión

11.1. Recursión
Una definición es recursiva cuando el concepto que se introduce está definido en base a sí
mismo. Un gran número de problemas se plantean de forma recursiva. Estosignifica que su
solución se apoya en la solución del mismo problema pero para un caso más fácil.
En matemáticas es frecuente definir conceptos en términos de sí mismos. Por ejemplo la
siguiente definición de factorial de un número n positivo es recursiva:

1, si n = 0
n!= 
n × (n − 1)!, si n ≠ 0
La definición es recursiva porque estamos definiendo el factorial de n como el producto de n
porel factorial de n-1, si n es distinto de cero. El concepto que definimos (factorial) aparece en
la propia definición. Si queremos calcular, por ejemplo, el factorial de 4 con la definición
anterior procederíamos del siguiente modo:

4! = 4 × 3! = 4 × 3 × 2! = 4 × 3 × 2 × 1! = 4 × 3 × 2 × 1 × 0! = 4 × 3 × 2 × 1 × 1 = 24
El siguiente ejemplo es una definición recursiva del sumatorio de los primeros nnúmeros
naturales:

0, si n = 0

n −1
i=
∑
n
i, si n ≠ 0
+
∑
i =0

i=0
n

Un último ejemplo es la definición de una potencia con exponente entero positivo:

1, si e = 0
be = 
b × b ( e −1) , si e ≠ 0
Vemos que la recursividad es una técnica que permite dar definiciones simples y elegantes. En
Modula-2 es posible definir subprogramas recursivos, es decir, subprogramas en cuyo cuerpoaparezcan llamadas a sí mismos.
La definición anterior de la función factorial nos lleva a la siguiente función Modula-2:
PROCEDURE Factorial (n : CARDINAL) : CARDINAL;
BEGIN
IF n = 0 THEN
RETURN 1
ELSE
RETURN n * Factorial(n-1)
END
END Factorial;

Obsérvese que hay una llamada a la propia función que se está definiendo (Factorial) en la
parte ELSE. Esto no presenta ningún problema ya que las reglas deámbito de Modula-2 lo
permiten.
Por otro lado, la función presenta más de una instrucción RETURN. Esta práctica es común a la
hora de escribir funciones recursivas. En el caso de funciones no recursivas, es mejor estilo de
programación utilizar una única sentencia RETURN al final del subprograma.
Veamos

ahora

que ocurre si un programa ejecuta
IO.WrCard(Factorial(3), 0) que llama a la función...