Recursividade – Algoritmo de Euclides recursivo

A recursividade é um recurso extremamente útil e poderoso tanto na matemática quanto na ciência da computação. Na informática, diz respeito a uma função que chama a si própria. Na matemática a um processo que é definido em termos de si mesmo. A melhor definição de recursividade, com os melhores exemplos, aquela que me fez realmente aprender a recursividade originou-se deste livro: Estruturas de dados usando C de Tenenbaum et al.  Maiores informações sobre recursividade podem ser obtidas aqui, aqui e aqui.

O algoritmo de Euclides demonstrado anteriormente tem uma versão recursiva bem elegante. Segue sua versão para o Visualg:

 algoritmo "Euclides recursivo"
// Função : Euclides Recursivo
// Autor :  Ed
// Data : 31/05/2009
// Seção de Declarações
var
a,b: inteiro

funcao mdc_rec (x:inteiro; y:inteiro):inteiro
var
dividendo,divisor: inteiro
inicio
dividendo<-x
divisor<-y
se divisor=0 entao
 retorne dividendo
senao
 retorne mdc_rec(divisor, dividendo%divisor)
fimse

fimfuncao

inicio
//entrada de dados
escreval()
escreval("Algoritmo de Euclides para encontrar o MDC entre 2 números")
escreval()
escreva("Digite o primeiro numero:")
leia (a)
escreva("Digite o segundo numero:")
leia (b)
escreval()
escreva ("O MDC de ", a," e ", b, " é ", mdc_rec(a,b))
escreval()
fimalgoritmo