Recursividad

Programaci´n Modular. ETSIT. 1o C, Apuntes o del profesor Juan Falgueras 2004

4 Recursividad
Contenido
4. Recursividad 4.1. Definici´n y Tipos de recursividad . . . . . . . . . . . o 4.1.1. La recursi´n es como la iteraci´n . . . . . . . . o o 4.1.2. Tipos de recursi´n . . . . . . . . . . . . . . . . o 4.1.3. Implementaci´n interna en un ordenador . . . . o 4.2. Verificaci´n de la correcci´nde un algoritmo recursivo o o 4.3. Conveniencia del uso de la recursividad . . . . . . . . 4.4. Ejemplos de programas recursivos . . . . . . . . . . . . 4.4.1. La funci´n de Fibonacci . . . . . . . . . . . . . o 4.4.2. D´ ıgitos binarios . . . . . . . . . . . . . . . . . . 4.4.3. La b´squeda binaria . . . . . . . . . . . . . . . u 4.4.4. Quicksort . . . . . . . . . . . . . . . . . . . . . 4.4.5.Torres de Hanoi . . . . . . . . . . . . . . . . . 4.4.6. Ackerman . . . . . . . . . . . . . . . . . . . . . 4.4.7. B´squeda binaria . . . . . . . . . . . . . . . . . u 4.5. Algoritmos de vuelta atr´s . . . . . . . . . . . . . . . . a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 2 3 4 5 5 5 7 7 8 11 12 12 12

4.

Recursividad
Hasta ahora hemos vistoformas de estructurar tanto datos como programas, mediante funciones. Las funciones resuelven cometidos concretos y llevan par´metros que las hacen ser a utiles para distintas situaciones. Las funciones que hemos visto hasta ahora se resolv´ por ´ ıan s´ mismas o, a lo sumo pod´ pedir ayuda otras funciones que terminaban resolvi´ndose sin ı ıan e m´s llamadas. Sin embargo, hay veces en que una funci´ns´lo se puede resolver volvi´ndose a o o e a llamar a s´ mismas. Se trata de funciones recursivas. ¿Cu´ndo tiene esto sentido? ı a En este tema se introduce el concepto de recursi´n, se examinan los posibles casos, se muestra o c´mo un ordenador, que es fundamentalmente iterativo, no recursivo, puede emular la recuro si´n; se dan reglas para comprobar que las solucines recursivas que se construyantengan final o y se presentan diversos ejemplos importantes de recursi´n. o

4.1.

Definici´n y Tipos de recursividad o

Se dice que un proceso es recursivo si se resulve llam´ndose a s´ mismo. a ı Para que la recursi´n tenga sentido (un final util) cada vez que se llame internamente a o ´ s´ misma deber´ hacerlo de una manera “menos recursiva” hasta que finalmente se llame a s´ misma ı a ı deuna manera no recursiva. La recursi´n infinita es in´til. o u Lo unico que determina el comportamiento de una funci´n son los par´metros que son los ´ o a que dan idea del “tama˜o del problema”. La funci´n no es recursiva para algunos valores del n o par´metro que se denominan casos base. Toda funci´n recursiva, pues, debe tener alg´n caso a o u base y toda llamada recursiva dentro de ella debetender hacia el caso base.

4.1

Definici´n y Tipos de recursividad o

2

4.1.1.

La recursi´n es como la iteraci´n o o

En muchas ocasiones se puede ver que la recursi´n no es m´s que la repetici´n (iteraci´n) o a o o de una serie de acciones. Esta iteraci´n se da hasta llegar a un valor de una variable. Pero en la o recursi´n esta iteraci´n se est´ desarrollando mediante la llamada dela funci´n a s´ misma con un o o a o ı par´metro que es la variable que determina el final de la recursi´n, en vez de ser un bucle dentro a o de una funci´n normal. As´ pues, en la iteraci´n, es la guarda del bucle la que determina cu´ndo o ı o a acabar´ la repetici´n; en la recursi´n es el par´metro. a o o a Por ejemplo: 1 x=0 f (x) = x · f (x − 1) x > 0 es una definici´n formal de la funci´n...