Nose

Ejercicios sobre recursividad

11 de febrero de 2003

1.

Implementa una funci´n recursiva que devuelva la suma de los d´
o
ıgitos
de un n´mero natural, que se le pasa por par´metro.
u
a

2.

Implementa una funci´n recursiva que imprima por pantalla los valores
o
desde 1 hasta un n´mero introducido por el usuario.
u

3.

Implementa una funci´n recursiva que imprima porpantalla los valores
o
desde un n´mero introducido por el usuario hasta 1.
u

4.

Implementa una funci´n recursiva que devuelva el n´mero de d´
o
u
ıgitos
de un n´mero natural.
u

5.

Implementa una funci´n recursiva que calcule el producto de dos n´meo
u
ros naturales (se supone que no est´ disponible el operador *).
a

6.

Implementa una funci´n recursiva que, dado un n´merobinario (reo
u
presentado mediante un entero), devuelva su valor en base decimal
(p.e. 101 = 5, 11111 = 31).

7.

Implementa una funci´n recursiva que devuelva el resultado de la sio
guiente expresi´n, para un n´mero natural x pasado por par´metro:
o
u
a
f (x) = x2 + (x − 1)2 + (x − 2)2 + . . . + 22 + 12

8.

Implementa una funci´n recursiva que lea desde teclado hasta encono
trarun car´cter de salto de l´
a
ınea (\n), y muestre por pantalla lo que
ha le´
ıdo, pero al rev´s (no utilizar vectores ni bucles).
e

9.

Implementa una funci´n recursiva que imprima por pantalla un n´meo
u
ro natural (se supone que s´lo est´ disponible la funci´n putchar).
o
a
o

10.

Implementa una funci´n recursiva que calcule el logaritmo entero de
o
un n´mero a en una baseb, ambos introducidos por el usuario. Ayuda:
u
ten en cuenta que logb (a/b) = logb a − logb b.

1

11.

Implementa una funci´n recursiva que, dado un n´mero natural, deo
u
vuelva otro n´mero que tenga los d´
u
ıgitos del primero, pero al rev´s.
e
Ayuda: utiliza un par´metro auxiliar, donde vayas acumulando los rea
sultados parciales.

12.

Implementa una funci´n que, dado unvector de TAM enteros, devuelo
va el m´
ınimo y el m´ximo. Ayuda: utiliza un par´metro auxiliar que
a
a
indique la porci´n del vector que has recorrido, y para que la funci´n
o
o
devuelva dos enteros, define una estructura.

13.

En el gran templo de Benar´s, bajo la c´pula que marca el centro
e
u
del mundo, se encuentra una bandeja de cobre en la que hay fijadas
tres agujas dediamante, cada una de un codo de alto y del grosor del
cuerpo de una abeja. En una de esas agujas, en la creaci´n, Dios puso
o
sesenta y cuatro discos de oro puro, estando el mayor sobre la bandeja
y los dem´s ordenados de mayor a menor sobre el primero. Esta es
a
la Torre de Brahma. D´ y noche sin parar los monjes mueven los
ıa
discos entre las agujas siguiendo las leyes inmutables de Brahma, queestablecen que el monje en activo no debe mover m´s de un disco a la
a
vez y que no puede poner un disco en una aguja que contenga un disco
menor. Cuando los sesenta y cuatro discos se hayan movido desde la
aguja original a una de las otras dos, la torre, el templo y los monjes
se convertir´n en cenizas, y con un trueno el mundo desaparacer´.
a
a
Con el tiempo, la Torre de Brahma se haconvertido en la Torre de
Hanoi.
a)

Implementa un algoritmo recursivo para solucionar el problema
de la Torre de Hanoi, para un n´mero de discos especificado por
u
par´metro.
a

b)

Calcula el n´mero de movimientos necesarios para resolver el prou
blema con n discos.

c)

Suponiendo que los monjes mueven un disco por segundo, ¿cu´nto
a
tiempo nos queda de vida? (seg´n las ultimasnoticias, el universo
u
´
tiene entre 13 y 14 mil millones de a˜os).
n

Nota: En Emacs, pulsa Alt-x y escribe hanoi. Prueba tambi´n a pulsar
e
Esc, luego :, y escribe (hanoi 5).
14.

Implementa una funci´n recursiva para mostrar por pantalla todas
o
las permutaciones de los caracteres de una cadena que se le pasa por
par´metro.
a

15.

La mayor´ de los tel´fonos m´viles...