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 lacorrecci´n de 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

4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
..
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
..
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

1
1
2
2
3
4
5
5
5
7
7
8
11
12
12
12

Recursividad
Hasta ahora hemos visto formas de estructurar tanto datos como programas, mediante funciones. Las funcionesresuelven 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´n s´lo se puede resolver volvi´ndose
a
o o
e
a llamar a s´ mismas. Setrata 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 construyan tengan final
o
y se presentan diversos ejemplos importantesde 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
ı
de una manera no recursiva.
La recursi´n infinitaes 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 debe tender hacia el caso base.

4.1Definici´n y Tipos de recursividad
o

4.1.1.

2

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 de la funci´n a s´ misma...