Trabajo Práctico de Recursión

Vista previa del material en texto

PRÁCTICA DE RECURSIVIDAD 
1) Realizar la Prueba de Escritorio y determinar que operación realiza el siguiente algoritmo: 
//x>=0, y>0 
 
 funcion_x (x,y: integer):integer; 
 begin 
 if (x =0) or (x<y) then 
 funcion_x:= 0 
 else 
 funcion_x := 1+ funcion_x (x-y, y); 
 end; 
2) Considere el siguiente procedimiento P: 
procedure P(num:integer); 
begin 
if (num>=1) and (num <=8) 
then 
begin 
 P(num-1); 
 write (num:1); 
end 
else 
 writeln 
 end {P}; 
Para responder las siguientes preguntas, realice la prueba de escritorio 
¿Qué salida producen las llamadas P(3), P(7), P(10): 
a) en el procedimiento original, 
b) si reemplazamos Num-1 por Num+1, 
c) si intercambiamos el write y la llamada recursiva, y 
d) si insertamos una copia de la instrucción write antes de la llamada recursiva. 
3) Dada la siguiente función realice la prueba de escritorio de llamadas y retornos de las funciones 
para (1,5) y F(8,3). 
Function F (Num1, Num2: integer): integer; 
begin 
if num1 > num2 then 
f:= 0 
else 
if num2 = num1 + 1 then 
f:= 1 
else 
f:= f (num1 + 1, num2 - 1) + 2 
end; 
 
 
4) Programe un método recursivo que transforme un número entero positivo a notación binaria. 
5) Escribir una función recursiva que devuelva la suma de los primeros N enteros. 
Para los siguientes ejercicios encontrar/plantear el caso base y la parte recursiva 
(no hacer el código) 
a) Un granjero ha comprado una pareja de conejos para criarlos y luego venderlos. Si la pareja de 
conejos produce una nueva pareja cada mes y la nueva pareja tarda un mes más en ser 
también productiva, ¿cuántos pares de conejos podrá poner a la venta el granjero al cabo de 
un año? 
b) Pensar una solución recursiva que calcule la cantidad de dígitos que tiene un número dado. 
c) Dado un vector de números enteros ordenado en forma ascendente y un número a buscar en 
dicho vector, implementar un proceso de búsqueda dicotómica en forma recursiva 
d) Plantear una solución recursiva para un programa que lea caracteres hasta el caracter "@" y los 
almacene en una cola. Una vez que finalizó la lectura se debe informar si la secuencia leída es 
capicúa.