Algoritmos e Estruturas de Dados I

Aula 13: Recursividade

Algoritmo recursivo é aquele que usa a si mesmo!!!

Só que com parâmetros diferentes: menores.

Idéia: determinar a solução para n elementos em função da solução para m < n elementos.

Exemplo: Fatorial

n! = 1 se n = 0;

n * (n - 1)! se n > 0.

program recursivo;

  function fatorial(n: integer):integer;
  begin
    if n = 0 then
      fatorial := 1;
    else
      fatorial := n * fatorial(n-1);
  end;

begin
  writeln('fatorial de 4: ',
          fatorial(4));
end.

Resultado: fatorial de 4: 24

Exemplo: Fatorial

program seguindo_recursividade;
  funtion fatorial(n: integer):integer;
  var f: integer;
  begin
    writeln('Calculo de fat(',n,')');
    if n = 0 then f := 1;
             else f := n * fatorial(n-1);
    writeln('fatorial de ',n,'=',f);
    fatorial := f;
  end;
begin
  writeln('fat(4) = ', fatorial(4));
end.
Resultado: Calculo de fat(4)

Calculo de fat(3)
Calculo de fat(2)
Calculo de fat(1)
calculo de fat(0)
fatorial de 0 = 1
fatorial de 1 = 1
fatorial de 2 = 2
fatorial de 3 = 6
fatorial de 4 = 24
fat(4) = 24

Exemplo: Fibonacci

O i-ésimo número é a soma dos dois anteriores:

Torre de Hanoi

Objetivo: Mover n discos de A para C, um de cada vez, sem que um disco maior fique sobre um menor.

Torre de Hanoi

program hanoi;
var n: integer;

  procedure movedisco(origem,destino
                             :integer);
  begin
    writeln(origem,' -> ', destino);
  end;

  procedure movetorre
           (altura,de,para,uso:integer);
  begin
    if altura > 0 then begin
      movetorre(altura-1,de,uso,para);
      movedisco(de,para);
      movetorre(altura-1,uso,para,de);
    end;
  end;

begin
  readln(n);
  movetorre(n, 1, 3, 2);
end.

Torre de Hanoi

Entrada: 3

Saída:

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

Recursividade

Variáveis locais são geradas dinamicamente a cada chamada do subprograma

Exemplo

program soma_recursiva;
const n = 5;
type lista = array [1..n] of integer;
var numero: lista;
    i: integer;

  function soma(var v: lista;
              ultimo: integer): integer;
  begin
    if ultimo = 1 then
      soma := v[1];
    else
      soma := v[ultimo] +
              soma(v,ultimo-1);
  end;

begin
  for i := 1 to n do read(numero[i]);
  writeln('soma = ', soma(numero, n));
end.

Entrada: 2 5 1 3 2
Saída: soma = 13

Labirinto

{Recursively find all exits from maze}
program ThreadTheMaze;
const MaxRow = 12;
      MaxCol = 12;
      PossiblePath = ` `;
      TheWayOut = `!';
type ArrayType = 
   array [1..MaxRow, 1..MaxCol] of char;
var Maze: ArrayType;

{ Reads the maze }
procedure StoreMaze(var Maze:ArrayType);
var i, j: integer;
begin
  for i := 1 to MaxRow do begin
    for j := 1 to MaxCol do
      read(Maze[i,j]);
    readln;
  end;
end;

Labirinto

{ Prints maze including exit }
procedure PrintMaze(Maze: ArrayType);
var i, j: integer;
begin
  for i := 1 to MaxRow do begin
    for j := 1 to MaxCol do
      write(Maze[i,j]);
    writeln;
  end;
end;

{ Tells if we are in an exit }
function IsExit(r,c:integer):boolean;
begin
  IsExit := (r in [1,MaxRow]) or
            (c in [1,MaxCol]);
end;

Labirinto

procedure Explore(Maze: ArrayType;
                  row,col: integer);
begin
  maze[row, col] := TheWayOut;
  if IsExit(row, col) then
    PrintMaze(Maze);
  else begin
    if Maze[row-1,col]=PossiblePath then
      Explore(Maze, row-1, col);
    if Maze[row,col+1]=PossiblePath then
      Explore(Maze, row, col+1);
    if Maze[row+1,col]=PossiblePath then
      Explore(Maze, row+1, col);
    if Maze[row,col-1]=PossiblePath then
      Explore(Maze, row, col-1);
  end;
end;

begin
  StoreMaze(Maze);
  Explore(Maze, 6, 6);
end.

Labirintos