EJERCICIOS DE RECURSIVIDAD

Por Jose A. Boquerini

Edición, variantes y soluciones por Jesús Alonso

Descríbase el efecto de los siguientes procedimientos y de las variantes que se se indican:

Procedure p1 ( a: integer );

begin

if a > 0 then

begin

writeln( a );

p1( a - 1 );

end

else writeln ( 'Fin' )

end;

¿Qué cambiaría al añadir estas dos lineas después de la instrucción `else ...'?:

writeln ( a ); writeln ( 'Fin de verdad' )

Procedure p2 ( a, b: integer );

begin

if a MOD b <> 0 then

begin

writeln ( a );

p2 ( a + 1, b );

end

else writeln ( 'Fin' )

end;

¿Qué cambiaría al eliminar el último else del programa?

Procedure p3 ( a, b: integer );

begin

if a > 0 then p3 ( a - 1, b + a )

else writeln ( b )

end;

¿Qué cambiaría al eliminar el último else del programa?

Procedure p4 ( a: integer );

begin

if a > 0 then

begin

p4 ( a - 1 );

writeln ( a );

end

else writeln ( '¿Fin?' );

end;

¿Qué cambiaría al eliminar el último else del programa?

Procedure p5 ( a, b: integer; c: real );

begin

if Abs ( a / b - c ) < 0.001

then writeln ( a, '/', b )

else if a / b < c

then p5 ( a + 1 , b, c )

else p5 ( a, b + 1, c )

end;

1ª llamada: p5 ( 1, 1, c ), c es real y mayor o igual que 0

Procedure p6 ( var a: integer );

begin

writeln ( a );

if a > 0 then a := a - 1

else if a < 0 then a := a + 1;

if a <> 0 then p1( a );

end;

¿Qué cambiaría si el parámetro `a' no estuviera pasado por referencia?

Ejecución de p1:

+-[_]--------------- P1.PAS

¦

¦ Program prueba;

¦

¦ Procedure p1 ( a: integer );

¦ begin

¦ if a > 0 then

¦ begin

¦ writeln( a );

¦ p1( a - 1 );

¦ end

¦ else writeln ( 'Fin' )

¦ end;

¦

¦ begin

¦ p1( 6 );

¦ end.

Salida de este programa para a = 6:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

6

5

4

3

2

1

Fin

Al añadir las siguientes dos ultimas instrucciones a p1:

-[_]------------------ P1.PAS modificado

Program prueba;

Procedure p1 ( a: integer );

begin

if a > 0 then

begin

writeln ( a );

p1( a - 1 );

end

else writeln ( 'Fin' );

writeln ( a );

writeln ( 'Fin de verdad' )

end;

begin

p1( 6 );

end.

Salida de este programa para a = 6:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

6

5

4

3

2

1

Fin

0

Fin de verdad

1

Fin de verdad

2

Fin de verdad

3

Fin de verdad

4

Fin de verdad

5

Fin de verdad

6

Fin de verdad

Ejecución de p2: ( la llamada es del tipo: if a > b then p2 ( Abs ( a ), Abs ( b ) ) )

+-[_]----------------P2.PAS

¦

¦ Program prueba;

¦

¦ Procedure p2 ( a, b: integer );

¦ begin

¦ if a MOD b <> 0 then

¦ begin

¦ writeln ( a );

¦ p2 ( a + 1, b );

¦ end

¦ else writeln ( 'Fin' )

¦ end;

¦

¦ begin

¦ a = 10;

¦ b := 8;

¦ if a > b then p2 ( abs( a ), abs ( b ) );

¦ end.

Salida de este programa para a = 10, b = 8:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

10

11

12

13

14

15

16

17

Fin

(Secuencia de numeros desde `a' hasta llegar al entero anterior a un divisor de `a + b' )

Al eliminar el último else del programa:

-[_]--------------- P2.PAS modificado

Program prueba;

Procedure p2 ( a, b: integer );

begin

if a MOD b <> 0 then

begin

writeln ( a );

p2 ( a + 1, b );

end;

writeln ( 'Fin' )

end;

begin

a = 10;

b := 8;

if a > b then p2 ( abs( a ), abs ( b ) );

end

Salida de este programa para a = 10, b = 8:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

10

11

12

13

14

15

Fin

Fin

Fin

Fin

Fin

Fin

Fin

¿Por qué se escribe 6 veces `Fin'?

Ejecución de p3:

+-[_]-----------------P3.PAS

¦

¦ Program prueba;

¦ var i:integer;

¦

¦ Procedure p3 ( a, b: integer );

¦ begin

¦ if a > 0 then p3 ( a - 1, b + a )

¦ else writeln ( b )

¦ end;

¦

¦ begin

¦ for i:= 1 to 10 do

¦ begin

¦ write ( `i = `, i:2, ` p3 = ` );

¦ p3 ( i, 0 )

¦ end;

¦ writeln ( `Fin' )

¦ end.

Salida de este programa para los siguientes valores de a y b = 0:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

i = 1 p3 = 1

i = 2 p3 = 3

i = 3 p3 = 6

i = 4 p3 = 10

i = 5 p3 = 15

i = 6 p3 = 21

i = 7 p3 = 28

i = 8 p3 = 36

i = 9 p3 = 45

i = 10 p3 = 55

Fin

Al eliminar el último else del programa:

-[_]--------------- P3.PAS modificado

Program prueba;

var i:integer;

Procedure p3 ( a, b: integer );

begin

if a > 0 then p3 ( a - 1, b + a );

writeln ( b )

end;

begin

for i:= 1 to 10 do

begin

writeln ( ' p3 ( ', i:2, ' ):' );

p3 ( i, 0 );

writeln;

end;

writeln ( `Fin' )

end.

¿Cúal sería la salida de este programa para los valores de a = 1..10 y b= 0?

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

i = 1 p3 : ?

i = 2 p3 : ?

i = 3 p3 : ?

i = 4 p3 : ?

i = 5 p3 : ?

i = 6 p3 : ?

i = 7 p3 : ?

i = 8 p3 : ?

i = 9 p3 : ?

i = 10 p3 : ?

Fin

Salida de este programa para los valores de a = 1..10 y b= 0:

p3 ( 1 ) :

1

0

p3 ( 2 ) :

3

2

0

p3 ( 3 ) :

6

5

3

0

p3 ( 4 ) :

10

9

7

4

0

p3 ( 5 ) :

15

14

12

9

5

0

p3 ( 6 ) :

21

20

18

15

11

6

0

p3 ( 7 ) :

28

27

25

22

18

13

7

0

p3 ( 8 ) :

36

35

33

30

26

21

15

8

0

p3 ( 9 ) :

45

44

42

39

35

30

24

17

9

0

p3 ( 10 ) :

55

54

52

49

45

40

34

27

19

10

0

Ejecución de p4:

+-[_]--------------- P4.PAS

¦

¦ Program Prueba;

¦

¦ Procedure p4 ( a: integer );

¦ begin

¦ if a > 0 then

¦ begin

¦ p4 ( a - 1 );

¦ writeln ( a );

¦ end

¦ else writeln ( '¿Fin?' );

¦ end;

¦

¦ begin

¦ p4 ( 5 );

¦ end.

Salida de este programa para a = 5:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

¿Fin?

1

2

3

4

5

Al eliminar el último else del programa:

-[_]-------------- P4.PAS modificado

Program Prueba;

Procedure p4 ( a: integer );

begin

if a > 0 then

begin

p4 ( a - 1 );

writeln ( a );

end;

writeln ( '¿Fin?' );

end;

begin

p4 ( 5 )

end.

La salida de este programa para a = 5 es:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

¿Fin?

1

¿Fin?

2

¿Fin?

3

¿Fin?

4

¿Fin?

5

¿Fin?

Ejecución de p5: ( 1ª llamada: p5 ( 1, 1, c ), c es real y mayor o igual que 0 )

+-[_]--------------------P5.PAS

¦

¦ Program prueba;

¦ var c:real;

¦

¦ Procedure p5 ( a, b: integer; c: real );

¦ begin

¦ if Abs ( a / b - c ) < 0.001

¦ then writeln ( a, '/', b )

¦ else if a / b < c

¦ then p5 ( a + 1 , b, c )

¦ else p5 ( a, b + 1, c )

¦ end;

¦

¦ begin

¦ c := 9.5;

¦ p5 ( 1, 1, c );

¦ writeln ( 'Fin' )

¦ end.

Salida de este programa para c = 9.5:

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

19/2

Fin

Ejecución de p6: (Calcular también la salida en el caso de que el parámetro no esté pasado por referencia)

+-[_]----------------------------- Referencia.PAS

¦

¦ Program prueba;

¦ var i: integer;

¦

¦ Procedure p6 ( var a: integer );

¦ begin

¦ writeln ( a );

¦ if a > 0 then a := a - 1

¦ else if a < 0 then a := a + 1;

¦ if a <> 0 then p1( a );

¦ end;

¦

¦ begin

¦ i := 9;

¦ p6 ( i );

¦ writeln ( 'i = ', i:2 );

¦ end.

¦

Salida de este programa para a = 9;

9

8

7

6

5

4

3

2

1

i = 0

Si el parámetro `a' ( a = 9 ) de p6 no estuviera pasado por referencia:

9

8

7

6

5

4

3

2

1

i = 9

ESTRUCTURAS DE DATOS-I Problemas de Recursividad. Nivel fácil

Dpt. OEI p-1-

ESCUELA UNIVERSITARIA DE INFORMÁTICA ESTRUCTURAS DE DATOS-I