Parte II: Recursão

Algoritmos Recursivos (continuação)

Vamos continuar o estudo de algoritmos recursivos. Nesse capítulo veremos mais exemplos. Diferente do capítulo anterior, nesse será apenas apresentado o algoritmos recursivo.

Séries

Seja \(\{x_i\}_{i=0}^\infty\) uma sequência de número reais. Defina outra sequência \(\{S_n\}_{n=0}^\infty\) como a soma dos \(n\) primeiros termos dessa sequência: \(S_n = \sum_{i=0}^n x_i\). A sequência \(\{S_n\}_{n=0}^\infty\) é chamada de série.

Nessa seção vamos usar a recursão para encontrar os termos de uma séria \(S_n = \sum_{i=0}^n x_i\) dada a sequência \(\{x_i\}\). Ou seja, para uma dada sequência \(\{x_i\}\) e um natural \(n\) estamos interessados em encontrar a soma dos \(n\) primeiros termos dessa sequência.

Veja que o \(n\)-ésimo termo da séria pode ser escrito como uma equção de diferenças: \[ S_n = S_{n-1} + x_n \] e essa será a ideia do algoritmo a seguir.

Como primeiro exemplo considere \(x_i = i\) e \(S_n = \sum_{i=0}^n x_i = \sum_{i=0}^n i\). Veja que para esse exemplo \(S_n = 0 + 1 + 2 + \ldots + n\). Vamos escrever um algoritmo que recebe como entrada \(n\) e retorna o \(n\)-ésimo termo dessa série, isto é, \(S_n\).

Entrada: n

Saída: \(S_n = 0 + 1 + 2 + ... + n\)

Nome: Serie1

1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0, retorne 0.
3. Retorne Serie1(n-1) + n

Veja que a chamada recursiva usa como argumento \(n-1\). Dessa forma garantimos a simplificação do argumento e que em algum momento chegaremos ao caso mais simples e o algoritmo termina.

Vejamos agora outro exemplo. Considere \(x_i = \frac{1}{i!}\) e defina \(S_n = \sum_{i=0}^n x_i = \sum_{i=0}^n \frac{1}{i!}\). Podemos criar um algoritmo recursivo e usar o computador para encontrar qualquer termo \(n\) dessa série, como mostra o pseudocódigo a seguir.

Entrada: n

Saída: \(S_n = \sum_{i=0}^n \frac{1}{i!}\)

Nome: Serie2

1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0, retorne 1.
3. Retorne Serie2(n-1) + 1/n!

Veja que no código acima consideram que já sabemos calcular \(n!\). Mas é verdade, já fizemos isso no capítulo anterior de forma recursiva. Então quando formos implementar esse último código no computador vamos chamar a função feita anteriormente que calcula \(n!\).

Já vimos em algumas disciplinas que a sequência \(S_n\) definida acima converge para o número irracional \(e=2.718282\ldots\), ou seja, \(S_n \xrightarrow[n \to \infty]{} e\). Se ainda não vimos veremos em breve. Então para \(n\) razoavelmente grande esperamos que \(S_n\) esteja próximo de \(e=2.718282\ldots\), como indica o limite. Com essa ideia podemos usar o algoritmo acima para encontrar uma aproximação para o número irracional \(e\), basta chamar a função com valores grandes de \(n\).

Maior Divisor Comum

Um algoritmo recursivo bem famoso é o Algoritmo de Euclides, conhecido desde a obra Elements de Euclides, por volta de 300 a.c. Este algoritmo calcula o maior divisor comum entre dois números sem precisar fatorá-los. Lembrando, o maior divisor comum (MDC) entre dois números inteiros é o maior número inteiro que divide ambos sem deixar resto.

O algoritmo de Euclides é baseado no princípio de que o MDC não muda se o maior número for subtraído do menor. Por exemplo, o MDC entre 252 e 105 é 21. Veja que \(252 = 21 \times 12\) e \(105 = 21 \times 5\). Também é verdade que o MDC entre 252 - 105 = 147 e 105 é 21. Veja que \(147 = 252 - 105 = 21 \times 12 - 21 \times 5 = 21 \times 7\).

A partir dessa ideia podemos afirmar que:

  • \(MDC(n,m) = MDC(m,n)\);
  • Se \(n=0\), \(MDC(n,m)=m\);
  • Se \(0 < n \le m\), \(MDC(n,m) = MDC(n,m-n) = MDC(m,m-n)\).

Podemos então criar uma função recursiva que encontra o \(MDC\) entre dois números inteiros quaisquer. \[ MDC(n,m) = \left\{ \begin{array}{ll} m & \hbox{, se } n=0\\ n & \hbox{, se } m=0\\ MDC(n,m-n) & \hbox{, se } n \le m\\ MDC(m,n-m) & \hbox{, se } m < n\\ \end{array} \right. \]

A partir da função acima podemos criar um pseudo-código recursivo que recebe como entrada dois números inteiros não negativos \(n\) e \(m\) e retorna o maior divisor comum entre eles. Atenção: se os dois números forem 0, não faz sentido falar em MDC entre eles.

Entrada: \(n\) e \(m\), inteiros não negativos

Saída: maior divisor comum entre \(n\) e \(m\)

Nome: MDC

1. Caso n ou m não seja inteiro não negativo, retorne erro.
2. Seja maior= maior entre n e m;
3. Seja menor= menor entre n e m;
4. Se maior=0, retorne erro (isso significa que m=n=0).
5. Se menor=0, retorne maior.
6. Retorne MDC(menor,maior-menor).

Veja que a chamada recursiva ocorre na linha 6 e que ambos os argumentos estão sendo simplificados. Isso nos faz garantir que em algum momento chega-se ao caso base, onde uma das entradas é zero.

Podemos melhorar ainda mais o desempenho do nosso algoritmo. Veja que se \(m\) é muito maior que \(n\) nossa chamada recursiva sera MDC\((n,m-n)\) várias vezes. Isso vai terminar quando já tivermos “tirado” todos os \(n\) que cabem dentro do \(m\). Ou seja, a última chamada recursiva desse tipo será MDC(n,m%%n)! Então se substituirmos na linha 6 maior-menor por maior%%menor (resto da divisão de maior por menor) vamos economizar muitos passos da recursão. Nesse caso o pseudocódigo mais ``enxuto’’ será:

Entrada: \(n\) e \(m\), inteiros não negativos

Saída: maior divisor comum entre \(n\) e \(m\)

Nome: MDC_rapido

1. Caso n ou m não seja inteiro não negativo, retorne erro.
2. Seja maior= maior entre n e m;
3. Seja menor= menor entre n e m;
4. Se menor=0, retorne maior.
5. Retorne MDC(menor,maior%%menor).

Torre de Hanoi

O problema ou quebra-cabeça conhecido como Torre de Hanói foi publicado em 1883 pelo matemático francês Edouard Lucas, também conhecido por seus estudos com a série Fibonacci.

O problema Consiste em transferir a torre composta por \(N\) discos, como na figura abaixo, do pino A (origem) para o pino C (destino), utilizando o pino B como auxiliar. Somente um disco pode ser movimentado de cada vez e um disco não pode ser colocado sobre outro disco de menor diâmetro.

Torre de Hanoi

Torre de Hanoi

Veja que se existe um único dico, \(N=1\), a solução é imediata: mova este disco de A para C. E se existirem \(N\) discos, quais os movimentos que devemos fazer? É isso que vamos tentar resolver.

Suponha que sabemos a sequência de movimentos para mover \(N-1\) discos de um pino origem para um pino destino. Então para mover os \(N\) discos do pino A para o pino C devemos primeiro mover os primeiros \(N-1\) discos de A para B. Em seguida mova o disco que sobrou no pino A para o pino C. Para terminar basta mover novamente os \(N-1\) discos, agora do pino B para o pino C. Veja figura a seguir.

Esquema Recursivo da Torre de Hanoi

Esquema Recursivo da Torre de Hanoi

Dessa forma foi definida uma solução recursiva para o problema:

  • Se \(N = 1\): mova um disco do pino A para o pino C.
  • Se \(N > 1\):
    • primeiro transfira \(N-1\) discos de A para B;
    • em seguida mova um disco do pino A para o pino C;
    • por último transfira \(N-1\) discos de B para C.

Baseado nessa ideia vamos escrever o pseudo-código que fornece a sequência de movimentos para transferir \(N\) discos do pino A (origem) para o pino C (destino).

Entrada: \(N\),A,C,B (número de discos, nome do pino origem, nome do pino destino e nome do pino auxiliar).

Saída: Sequência de movimentos (que pode ser guardados em um array de "character")

Nome: Hanoi

1. Caso N não seja inteiro positivo, retorne erro.
2. Se N = 1, realize o movimento: "mova um disco do pino A para o pino C e fim".
3. Realize os movimentos de Hanoi(N-1,A,B,C)
4. Realize o movimento: "mova um disco do pino A para o pino C"
5. Realize os movimentos de Hanoi(N-1,B,C,A).

Vamos ver como fica esse algoritmo implementado no R.

Hanoi = function(N,A,C,B){
  if(N%%1 != 0 || N <=0)
    stop("N tem que ser um inteiro positivo")
  if(N==1)
    return(paste("mova um disco do pino ",A," para o pino", C,"."))
  
  movimentos_parte_1 = Hanoi(N-1,A,B,C)
  movimentos_parte_2 = paste("mova um disco do pino ",A," para o pino", C,".")
  movimentos_parte_3 = Hanoi(N-1,B,C,A)
  
  return(c(movimentos_parte_1,movimentos_parte_2,movimentos_parte_3))
}


Hanoi(2,"A","C","B")
## [1] "mova um disco do pino  A  para o pino B ."
## [2] "mova um disco do pino  A  para o pino C ."
## [3] "mova um disco do pino  B  para o pino C ."

Veja que os argumentos de entrada são os nomes dos pinos, por isso eles entram como texto.

Hanoi(3,"Inicio","Fim","Aux")
## [1] "mova um disco do pino  Inicio  para o pino Fim ."
## [2] "mova um disco do pino  Inicio  para o pino Aux ."
## [3] "mova um disco do pino  Fim  para o pino Aux ."   
## [4] "mova um disco do pino  Inicio  para o pino Fim ."
## [5] "mova um disco do pino  Aux  para o pino Inicio ."
## [6] "mova um disco do pino  Aux  para o pino Fim ."   
## [7] "mova um disco do pino  Inicio  para o pino Fim ."

Se quiser, testes os movimentos do seu programa no site https://www.mathsisfun.com/games/towerofhanoi.html.