Programa com recursividade

As linguagens de programação modernas disponibilizam estruturas de repetição para o programador. No entanto, é possível simular qualquer repetição com funções, procedimentos, ou métodos recursivos. Por isso, esse artigo mostra um exemplo construido com recursividade, sem nenhum comando de repetição.

Um pouco sobre recursividade

As funções e procedimentos recursivos são chamadas dentro da própria função ou procedimento.

Exemplo:

procedure recursividade;
begin
  recursividade;
end;

O procedimento recursividade é chamado no corpo do próprio procedimento. No entanto, esse procedimento recursivo gera um loop infinito. Isto é, leva o programa a travar. Por isso, normalmente, as funções ou procedimentos recursivos têm uma condição de parada para evitar o loop infinito.

Por exemplo: como criar um procedimento em pascal que imprime os números de um a um número informado pelo usuário?

Abaixo a solução com comando "for":

program IMP_NUMS;
uses crt;

procedure imprime_numeros( n : integer);
begin
  for i := 1 to n do
    write( i,' ' );
end;

begin
  clrscr;
  write( 'Informe um numero: ' );
  readln( num );

  imprime_numeros( num );
  readln;
end.

Abaixo a solução com procedimento recursivo:

program IMP_NUMS_RECURSIVO;
uses crt;

procedure imprime_numeros( n : integer; i : byte );
begin
  if ( i <= n ) then    
    begin
      write( i,' ' );
      imprime_numeros( n, i+1 );
    end;
end;

begin
  clrscr;
  write( 'Informe um numero: ' );
  readln( num );

  imprime_numeros( num, 1 );
  readln;
end.

Perceba que nas duas soluções são necessárias uma variável contador que foi nomeada "i" e uma condição de parada que é quando o contador "i" torna-se igual ao número "n". Perceba que na versão recursiva o contador é inicializado com 1 e passado como segundo parâmetro para o procedimento "imprime_numeros", enquanto que, na versão não recursiva a variável contador é criada no próprio procedimento, necessitando apenas de um número como parâmetro. A variável contador, nas duas soluções, tem seu valor variado de 1 até o numero "n". Perceba também que o procedimento recursivo recebe um parâmetro a mais no programa principal. Ou seja, a variavel contador "i" é inicializada com valor 1 no programa principal.

Na função recursiva, o contador "i" é incrementado em 1 quando a função imprime_numeros é chamada de modo recursivo recebendo o parâmetro "i+1".

Abaixo um programa que fiz inteiramente com recursividade ( Sem nenhuma estrutura de repetição ):

Imagem capturada do programa:

O código fonte escrito em linguagem pascal:

program RECURSIVIDADE ;
uses crt;

type tvetor = array[ 1..100 ] of integer;

procedure imprime_numeros( n : word; i : byte );
begin
  if ( i <= n ) then
    begin
      write( i,' ' );
      imprime_numeros( n, i+1 );
    end;
end;

procedure imprime_divisores( n : word; i : byte );
begin
  if ( i <= n div 2 ) then
    begin
      if ( n mod i = 0 ) then
        write( i,' ' );
      
      imprime_divisores( n, i+1 );
    end
  else write( n );
end;

procedure eh_primo( n : word; i : byte; var eh : boolean );
begin
  if ( eh ) and ( i <= n div 2 ) then
    begin
      if ( n mod i = 0 ) then
        eh := false
      else eh_primo( n, i+1, eh );
    end;
end;

procedure imprime_primos( n : word; i : byte );
var eh_p : boolean;
begin
  if ( i <= n ) then
    begin
      eh_p := true;
      eh_primo( i, 2, eh_p );
      if ( eh_p ) then
        write( i,' ' );
      
      imprime_primos( n, i+1 );
    end;
end;

procedure sorteia_numeros( var vet : tvetor; max : word; tam, i : byte );
begin
  if ( i <= tam ) then
    begin
      vet[ i ] := random( max );
      sorteia_numeros( vet, max, tam, i+1 );
    end;
end;

procedure imprime_vetor( vet : tvetor; tam, i : byte );
begin
  if ( i <= tam ) then
    begin
      write( vet[ i ], ' ' );
      imprime_vetor( vet, tam, i+1 );
    end;
end;

procedure eh_palindromo( palavra : string; i : byte; var eh : boolean );
begin
  if ( eh ) and ( i <= length( palavra ) div 2 ) then
    begin
      if ( palavra[ i ] <> palavra[ length( palavra ) - i + 1 ] ) then
        eh := false
      else eh_palindromo( palavra, i+1, eh );
    end;
end;

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

function fibo( n : word ) : word;
begin
  if ( n = 0 ) or ( n = 1 ) then
    fibo := 1
  else fibo := fibo( n-1 ) + fibo( n-2 );
end;

procedure imprime_serie_fibo( n : word; i : byte );
begin
  if ( i <= n ) then
    begin
      write( fibo( i ),' ' );
      imprime_serie_fibo( n, i+1 );
    end;
end;

procedure indice_do_maior( vet : tvetor; tam, i : byte; menor : integer; var indice : byte );
begin
  if ( i <= tam ) then
  begin
    if ( vet[ i ] < menor ) then
      begin
        indice := i;
        indice_do_maior( vet, tam, i+1, vet[ i ], indice );
      end
    else indice_do_maior( vet, tam, i+1, menor, indice );
  end;
end;

procedure ordena( var vet : tvetor; tam, i : byte );
var indice : byte;
aux : integer;
begin
  if ( i <= tam ) then
    begin
      indice := i;
      indice_do_maior( vet, tam, i+1, vet[ i ], indice );
      
      aux := vet[ i ];
      vet[ i ] := vet[ indice ];
      vet[ indice ] := aux;
      
      ordena( vet, tam, i+1 );
    end;
end;

procedure menu;
begin
  clrscr;
  writeln( '********************* Menu *********************' );
  writeln;
  writeln( ' (1) - Imprime numeros menores ou iguais a' );
  writeln( ' (2) - Imprime os primos menores ou iguais a' );
  writeln( ' (3) - Imprime divisores' );
  writeln( ' (4) - Verifica se eh palindromo' );
  writeln( ' (5) - Imprime fatorial' );
  writeln( ' (6) - Imprime serie fibbonacci' );
  writeln( ' (7) - Imprime ordenado' );
  writeln( ' (0/Esq) - Sair' );
  writeln;
  writeln( '************************************************' );
  writeln;
end;

{ ****** PROGRAMA PRINCIPAL ****** }


procedure prog_principal;

  const VET_QUANT: integer = 20;
  VET_MAX : integer = 100;

  var op : char;
  num : word;
  palavra : string;
  eh_p : boolean;
  fat : word;

  vet : tvetor;
  vtam : byte;

  Begin
    menu;
    op := readkey;
    if ( op <> '0' ) and ( op <> #27 ) then
    begin
      case op of
        '1': begin
          write( 'Informe um numero: ' );
          readln( num );
          
          writeln;
          write( 'Numeros: ' );
          imprime_numeros( num, 1 );
          readln;
        end;
        '2': begin
          write( 'Informe um numero: ' );
          readln( num );
          
          writeln;
          write( 'Primos: ' );
          imprime_primos( num, 1 );
          readln;
        end;
        '3': begin
          write( 'Informe um numero: ' );
          readln( num );
          
          writeln;
          write( 'Divisores de ',num,': ' );
          imprime_divisores( num, 1 );
          readln;
        end;
        '4': begin
          write( 'Informe uma palavra: ' );
          readln( palavra );
          
          eh_p := true;
          eh_palindromo( palavra, 1, eh_p );
          
          writeln;
          if ( eh_p ) then
            writeln( 'A palavra ',palavra,' eh palindromo' )
          else writeln( 'A palavra ',palavra,' nao eh palindromo' );
          readln;
        end;
        '5': begin
          write( 'Informe um numero: ' );
          readln( num );
          
          fat := fatorial( num );
          
          writeln;
          writeln( 'O fatorial de ',num,' eh: ', fat );
          readln;
        end;
        '6': begin
          write( 'Informe um número: ' );
          readln( num );
          
          writeln;
          write( 'Serie fibbonacci: ' );
          imprime_serie_fibo( num, 0 );
          readln;
        end;
        '7': begin
          sorteia_numeros( vet, VET_MAX, VET_QUANT, 1 );
          
          writeln;
          write( 'Numeros sorteados: ' );
          imprime_vetor( vet, VET_QUANT, 1 );
          
          ordena( vet, VET_QUANT, 1 );
          
          writeln;
          write( 'Numeros ordenados: ' );
          imprime_vetor( vet, VET_QUANT, 1 );
          readln;
        end;        
    end;
    
    prog_principal;
  end;
End;

Begin
  prog_principal;
End.

Baixe o código fonte aqui.

Finalizando...

É isso pessoal. Peço que quem tiver gostado, envie um comentário logo abaixo.

Até o próximo