RECURSIVIDAD

 

 

 

 

 

 

 

 

 

 

 

 

 

 

...De todas formas, los algoritmos recursivos son apropiados principalmente cuando el problema a resolver, o la función a calcular, o la estructura de datos a procesar, están ya definidos de forma recursiva.

 

Niklaus Wirth

 

OBJETIVOS DE ESTE CAPITULO:

 

 

 

 

 

INDICE TEMA-3   Recursividad. 4 horas.   1. Definición de Recursividad   2. Recursividad Directa e Indirecta   3. Funcionamiento Interno 4. Ejemplos

 

 

1. RECURSIVIDAD. Definición.

 

 

Ø Tipo de datos RECURSIVO  à Se define en función de sí mismo.

 

 

= Ej: Definición recursiva de los números Naturales:

 

a) 1 es un número Natural

 

b) El siguiente de un número natural es un número natural

 

= Ej: Declaración recursiva de un Árbol:

 

a) Un nodo vacío es un árbol:

 

b) Si t₁ y t₂ son árboles, entonces

 

 

 

También es un árbol

 

 

Ø Procedimiento o Función RECURSIVOS  à En su interior se encuentra una llamada al mismo procedimiento o función.

 

 

 

 

2. RECURSIVIDAD Directa e Indirecta.

 

 

 

Ø Directa:

 

Procedure Directa ( ... );

begin

         .

         .

         .

         Directa ( ... );

         .

         .

         .

end;

 

 

 

Ø Indirecta:

 

Procedure Indirecta ( ... );

begin

    .

    .

    .

    A ( ... );

    .

    .

    .

end;

 

Procedure A ( ... );

begin 

.

.

.

Indirecta ( ... );

.

.

.

end;

 

$ ¿Có mo puede ocurrir esto?

 

3. Funcionamiento Interno.

 

 

 

 

 

 

 

 

Ø Puntos importantes a tener en cuenta

 

 

= Condición de parada

 

= Parámetros que se pasan en cada llamada

 

= Marcha atrás (backtracking)

 

= Consumo de memoria

 

= ...
4. EJEMPLOS.

 

Ø Función Factorial:

 

 

= Formulación:

 

 

Función Factorial ( n! ) para enteros no negativos:

 

a) 0! = 1

 

b) si n > 0 entonces n! = n _* ( n - 1 )!

 

 

Program Factorial;

 

Const n = 8;

 

Function Fact ( N: Integer ): Integer;

begin

         if N = 0 then Fact := 1

         else Fact := N _* Fact ( n - 1 )

end;

 

begin

         writeln ( Fact ( N ) )

end.

 

 

 

Ø Función Potencia:

 

= Formulación:

 

Función Potencia ( aⁿ ) de exponente no negativo:

 

a) a⁰ = 1

 

b) si n > 0 entonces aⁿ = a _* a^{n - 1}

 

 

Program Potencia;

 

Const base = 5;

  n = 10;

 

Function Pot ( a, N: Integer );

begin

         if N = 0 then Pot := 1

         else  Pot := a * Pot ( a, N - 1 );

end;

 

begin

         writeln( Pot ( base, n ) )

end.

Ø Función Torres de Hanoi:

 

= Formulación:

    

 

Nunca una ficha más ancha encima de otra más estrecha!.

 

 

Program Hanoi;

 

var NFichas, PaloI, PaloF; Integer;

 

Procedure Mover ( NFichas, PaloI, PaloF: Integer);

begin

         if NFichas = 1 then writeln ( ‘Mover de ‘, PaloI, ‘a‘, PaloF );

         else begin

                       Mover ( NFichas - 1, PaloI, 6 - PaloI - PaloF );

                       writeln ( ‘Mover de ‘, PaloI, ‘a ‘, PaloF );

                       Mover ( NFichas - 1, 6 - PaloI - PaloF, PaloF )

                end

end;

 

begin (* Hanoi *)

          writeln;

          writeln ( ‘introducir el número de fichas: ‘);

          read ( NFichas );

          PaloI := 1; PaloF := 3;

          Mover ( Nfichas, PaloI, PaloF )

end.