Estudando recursividade direta e indireta

Uma rápida explicação e demonstração de como funciona a recursividade para programas em C especialmente, usando como exemplo o algoritmo de Euclides para o cálculo do MDC.

[ Hits: 31.447 ]

Por: Carlos Roberto S. Junior em 29/02/2008


Introdução



A recursividade é um recurso muito importante para a programação, é uma maneira de se visualizar uma solução para determinado problema. Há diversas vantagens no uso da recursividade, tais como o estudo da complexidade algorítmica, visualização do algoritmo etc. Porém a recursividade pode causar rompimento na pilha de memória.

Para exemplificar com funciona a recursividade simples utilizaremos o algoritmo do cálculo do MDC pelo método de Euclides. Em linguagem algorítmica seria algo como:

Algoritmo EuclidesMDC
|  {Faz o cálculo do MDC seguindo Euclides}
|início
|
|função calculoMDC(valorA: inteiro, valorB: inteiro): inteiro
||início
||     se valorB = 0 então
||     |      calculoMDC <- valorA
||     |senão
||     |      calculoMDC <- calculoMDC(valorB, valorA mod valorB)
||     fim-se
|fim-função
fim

O Algoritmo de Euclides nada mais faz que pegar dois números e dividí-los, o resto da divisão de A por B é testado se for zero, então o algoritmo retorna o menor valor como sendo o MDC, se for diferente de zero, o maior valor é jogado no caso A e B assume seu lugar, o resto da divisão de A por B assume o lugar de B e a função é chamada novamente até que o resto da divisão seja zero.

Faça o teste de mesa e verá que o algoritmo proposto apesar de simples cobre grande parte dos casos. Só não funcionará para números negativos pois "mod" não está definido para eles, segundo a matemática discreta.

    Próxima página

Páginas do artigo
   1. Introdução
   2. Recursividade direta ou simples
   3. Recursividade indireta ou composta
Outros artigos deste autor

Alocação dinâmica de memória em C

Leitura recomendada

Dynamic libraries com libtool

Como funcionam os alocadores de memória do STD C?

Projeto Icecream (parte 1)

Acessando a porta paralela via Linux

Utilizando técnicas recursivas em C e C++

  
Comentários
[1] Comentário enviado por f_Candido em 29/02/2008 - 18:25h

Legal.... Parabéns... Objetivo e eficiente.

Abraços


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts