Exercícios Resolvidos de Definindo funções recursivas

Ver Teoria

Enunciado

O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando-se uma definição recursiva:

M D C x ,   y = M D C x - y ,   y   s e   x > y

Além disso, sabe-se que:

M D C x ,   y = M D C ( y ,   x )

M D C x ,   x = x

Passo 1

Vamos lá, a primeira coisa que nós temos que fazer para criarmos essa função é definir o escopo da nossa função.

Com isso, sabemos que se trata de uma função com retorno de valor inteiro (o M.D.C) chamada m d c que recebe como parâmetros dois números inteiros x e y como parâmetro.

Passo 2

Agora que já temos uma visão geral da nossa função, podemos definir o caso básico que limitará as chamadas recursivas.

Um aspecto super interessante desse exercício é que podemos utilizar como caso básico uma das propriedades dadas no enunciado, que é M D C x ,   x = x . No caso, se durante as instâncias da recursão obtermos x igual a y , basta retornamos x como máximo divisor comum.

Passo 3

Com o nosso caso básico prontinho, podemos definir a regra que irá criar as instâncias recursivas.

Basicamente nós simplesmente temos que fazer a verificação de x é maior que y . Caso seja, utilizamos a regra M D C x ,   y = M D C ( x - y ,   y ) , caso contrário, temos que utilizar a regra M D C x ,   y = M D C ( y - x ,   x ) . Utilizando essa regra de criação de instância, chegaremos em um momento em que x = y , ou seja, temos o valor do máximo divisor comum.

Resposta

Ei, a resposta está no passo a passo :)