ingenieria de software

Programaci´on Modular. ETSIT. 1o C, Apuntes
del profesor Juan Falgueras 2004
4
Recursividad
Contenido
4. Recursividad 1
4.1. Definici´on y Tipos de recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
4.1.1. La recursi´on es como la iteraci´on . . . . . . . . . . . . . . . . . . . . . . . . 2
4.1.2. Tipos de recursi´on . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 2
4.1.3. Implementaci´on interna en un ordenador . . . . . . . . . . . . . . . . . . . . 3
4.2. Verificaci´on de la correcci´on de un algoritmo recursivo . . . . . . . . . . . . . . . . 4
4.3. Conveniencia del uso de la recursividad . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4. Ejemplos de programas recursivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4.1.La funci´on de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4.2. D´ıgitos binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.4.3. La b´usqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.4.4. Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.4.5. Torres de Hanoi . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4.6. Ackerman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4.7. B´usqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5. Algoritmos de vuelta atr´as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4. Recursividad
Hasta ahora hemos visto formasde estructurar tanto datos como programas, mediante funciones.
Las funciones resuelven cometidos concretos y llevan par´ametros que las hacen ser
´utiles para distintas situaciones. Las funciones que hemos visto hasta ahora se resolv´ıan por
s´ı mismas o, a lo sumo pod´ıan pedir ayuda otras funciones que terminaban resolvi´endose sin
m´as llamadas. Sin embargo, hay veces en que una funci´ons´olo se puede resolver volvi´endose
a llamar a s´ı mismas. Se trata de funciones recursivas. ¿Cu´ando tiene esto sentido?
En este tema se introduce el concepto de recursi´on, se examinan los posibles casos, se muestra
c´omo un ordenador, que es fundamentalmente iterativo, no recursivo, puede emular la recursi
´on; se dan reglas para comprobar que las solucines recursivas que se construyantengan final
y se presentan diversos ejemplos importantes de recursi´on.
4.1. Definici´on y Tipos de recursividad
Se dice que un proceso es recursivo si se resulve llam´andose a s´ı mismo.
Para que la recursi´on tenga sentido (un final ´util) cada vez que se llame internamente a
s´ı misma deber´a hacerlo de una manera “menos recursiva” hasta que finalmente se llame a s´ı misma
de una manera norecursiva.
La recursi´on infinita es in´util.
Lo ´unico que determina el comportamiento de una funci´on son los par´ametros que son los
que dan idea del “tama˜no del problema”. La funci´on no es recursiva para algunos valores del
par´ametro que se denominan casos base. Toda funci´on recursiva, pues, debe tener alg´un caso
base y toda llamada recursiva dentro de ella debe tender hacia el casobase.
4.1 Definici´on y Tipos de recursividad 2
4.1.1. La recursi´on es como la iteraci´on
En muchas ocasiones se puede ver que la recursi´on no es m´as que la repetici´on (iteraci´on)
de una serie de acciones. Esta iteraci´on se da hasta llegar a un valor de una variable. Pero en la
recursi´on esta iteraci´on se est´a desarrollando mediante la llamada de la funci´on a s´ı misma con unpar´ametro que es la variable que determina el final de la recursi´on, en vez de ser un bucle dentro
de una funci´on normal. As´ı pues, en la iteraci´on, es la guarda del bucle la que determina cu´ando
acabar´a la repetici´on; en la recursi´on es el par´ametro.
Por ejemplo:
f(x) =
(
1 x = 0
x · f(x − 1) x > 0
es una definici´on formal de la funci´on factorial en forma recursiva. que podr´ıa...