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

Italo Info

Um pouco sobre recursividade

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

O código fonte escrito em linguagem pascal:

Finalizando...