Na ciência da computação um algoritmo é dito recursivo quando ele chama a si próprio com entradas mais simples. De forma semelhante, dizemos que uma função é implementada de forma recursiva quando ela chama a si própria com argumentos mais simples.
Veremos que para todo algoritmo recursivo existe outro, que executa a mesma tarefa, de forma não recursiva. A vantagem em usar os algoritmos recursivos é a maior simplicidade e clareza no código (confira!). A desvantagem é que em geral tais algoritmos consomem muita memória, devido ao uso intensivo de pilha.
Nessa segunda parte veremos alguns algoritmos recursiva. O objetivo é revisitar alguns algoritmos já estudados em capítulos anteriores e aprender outros novos, todos de forma recursiva.
Nesse primeiro capítulo vamos explorar alguns exemplos mais simples de algoritmos recursivos. Todo os exemplos apresentados têm um único argumento de entrada e retornam um único obejto na saída, e não uma lista com vários objetos.
O exemplo mais clássico em recursão é o cálculo do fatorial de \(n\). Podemos fazer isso de forma recursiva ou não. Vejamos primeiro o algoritmo sem recursão.
Entrada: n
Saída: !n = n x (n-1) x … x 2 x 1.
1. Caso n não seja inteiro não negativo, retorne erro.
2. Inicie fat = 1;
3. Se n=0, retorne fat.
4. Inicie i = 1;
5. Faça fat = fat*i;
6. Incremente i = i + 1;
7. Se i <= n, volte para a linha 5;
8. Retorne fat.Veja como fica o código dessa função no R:
fatorial = function(n){
if(!is.numeric(n))
stop("o argumento de entrada tem que ser numérico.")
if(n<0)
stop("o argumento de entrada tem que ser um número não negativo")
fat = 1
if(n == 0)
return(fat)
for(i in 1:n){
fat = fat*i
}
return(fat)
}Veja agora o algoritmo recursivo. Para que o pseudocodigo fique claro, vamos também definir o nome de função nele.
Entrada: n
Saída: !n = n x (n-1) x … x 2 x 1.
Nome: fatorial_rec
1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0, retorne 1.
3. Retorne n*fatorial_rec(n-1)Veja que a chamada recursiva aparece na linha 3. A função fat-rec, que está sendo definida para uma entrada n, é chamada para a entrada n-1. Ou seja, o algoritmo chama a si próprio com o argumento de entrada simplificado. Dessa forma garantimos que em algum momento a função fat-rec será chamada para n=0, argumento para o qual temos resposta imediata, 1.
O código para a função recursiva fica assim:
fatorial_rec = function(n){
if(!is.numeric(n))
stop("o argumento de entrada tem que ser numérico.")
if(n<0)
stop("o argumento de entrada tem que ser um número não negativo")
if(n == 0)
return(1)
return(n*fatorial_rec(n-1))
}fatorial(5)## [1] 120fatorial_rec(5)## [1] 120Também podemos usar a recursão para trabalhar com vetores. Veja primeiro o pseudo-código sem usar recursão, como já fizemos anteriormente.
Entrada: v
Saída: O maior elemento de v
Nome: maior
1. Defina n como o tamanho do vetor v;
2. Defina max = v[1]
3. Inicie i = 2
4. Se v[i] > max, faça max = v[i];
5. Incremente i = i + 1;
6. Se i <=n, volte para a linha 4;
7. Retorne max.Agora veja outro algoritmo, esse recursivo, que executa a mesma coisa.
Entrada: v
Saída: O maior elemento de v
Nome: maior_rec
1. Defina n como o tamanho do vetor v;
2. Se n = 1, retorne v[1];
3. Defina w = v[2:n];
4. max_w = maior_rec(w);
5. Se v[1] > max_w, retorne v[1].
6. Retorne max_w.Veja que a chamada recursiva aparece na linha 4. Nesse exemplo o argumento foi simplificado uma vez que vetor passado como argumento de entrada tem sempre uma dimensão a menos. Assim garantimos que em algum momento a função será chamada para um vetor de tamanho 1, entrada para a qual temos uma resposta imediata.
Uma sequência de números reais \(\{x_n\}_{n=1}^\infty\) é definida a partir de uma equação de diferenças quando o seu \(n\)-ésimo termo é escrito em função de termos anteriores. Ou seja, quando existe \(f\) tal que \(x_n = f(n,x_{n-1},x_{n-2},\ldots)\).
Um exemplo de equação de diferenças é a sequência de Fibonacci, que já foi vista em capítulos anteriores. Esse exemplo será revisto em breve. Antes disso vejamos alguns outros exemplos.
Encontrar a solução de uma equação de diferenças consiste em determinar o \(n\)-ésimo termo da sequência de forma direta, sem depender dos termos anteriores, dependendo apenas de \(n\). Para isso existem muitas técnicas, mas aprender essas técnicas não é o foco do nosso curso.
Por exemplo, seja \(\{x_n\}_{n=1}^\infty\) uma sequência definida por: \[x_0 = 1 \qquad \hbox{ e } \qquad x_n = 2x_{n-1} + 1.\] Com essas informações podemos calcular todos os termos de forma iterativa: \[ \begin{array}{ll} x_0 = 1, \\ x_1 = 2 \times 1 + 1 = 3, \\ x_2 = 2 \times 3 + 1 = 7, \\ x_3 = 2 \times 7 + 1 = 15, \ldots \end{array} \]
A solução dessa equação de diferenças é \(x_n = 2^n - 1\) (verifique!). Mas nesse curso não vamos aprender como chegar nessa solução, nosso trabalho será montar a equação e resolver o problema de forma iterativa a partir de uma função implementada no R. Faremos isso usando e não usando recursão. Vejamos a seguir alguns problemas que utilizam equações de diferenças em sua modelagem.
Matemática Financeira
Em Matemática Financeira muitos problemas que envolvem juros, como investimentos ou dívidas, podem ser expressos em termos de sequências de diferenças. Veja dois exemplos a seguir.
Suponha que você investiu R$ 1.000,00 em um fundo de investimento que paga \(0,7\%\) de rendimento ao mês. Considere \(x_n\) como sendo o total acumulado após \(n\) meses de investimento. Primeiro veja que o total acumulado após \(n\) meses depende diretamente do total acumulado após \(n-1\) meses: \[\begin{align*} x_0 &= 1.000,00\\ x_n &= x_{n-1} + 0,007 \times x_{n-1} = 1,007 \times x_{n-1}\\ \end{align*}\]
Essa é uma equação de diferenças homogênea de primeira ordem com coeficiente constante, ou seja, ela é do tipo: \(x_n = cx_{n-1}\) com \(c \in \mathbb{R}\). Toda equação desse tipo tem uma solução fácil: \(x_n = c^nx_0\) (verifique!). Mas não é isso que estamos buscando. Nesse capítulo queremos treinar a implementação de algoritmos usando recursão. Vamos então escrever um código que recebe como entrada \(n\) e retorna \(x_n\), onde cada \(x_i\) é calculado de forma iterativa, como se não soubéssemos a solução da equação de diferenças.
Veja primeiro o pseudo-código sem usar recursão.
Entrada: n
Saída: Xn = total acumulado após n meses de investimento, considerando juros de 0,7% ao mês e investimento incial de R$ 1.000,00.
Nome: Investimento
1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0 retorne 1000;
3. Defina x = 1000;
4. Faça i=1;
5. Faça x = 1.007 * x;
6. Incremente i = i + 1;
7. Se i <= n, volte para a linha 5;
8. Retorne x.Agora um pseudocodigo recursivo que executa a mesma tarefa.
Entrada: n
Saída: Xn = total acumulado após n meses de investimento, considerando juros de 0,7% e investimento incial de R$ 1.000,00.
Nome: Investimento_rec
1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0, retorne 1000;
3. Retorne 1.007*Investimento_rec(n-1)Vejamos agora outro exemplo envolvendo juros: um financiamento.
Suponha que você vai pegar emprestado R$1.000,00 no banco e deverá pagar esse valor corrigido por um juros composto de 1,5% ao mês. Ou seja, a cada mês sua dívida cresce 1,5%. Suponha que você está disposto a pagar parcelas mensais de R$ 200,00.
Considere \(y_n\) como sendo sua dívida após \(n\) meses do início do financiamento. Primeiro veja que a dívida após \(n\) meses depende diretamente da dívida após \(n-1\) meses: \[\begin{align*} y_0 &= 1.000,00\\ y_n &= y_{n-1} + 0,015 \times y_{n-1} - 200 = 1,015 \times y_{n-1} - 200 \end{align*}\]
Com essas informações podemos escrever um pseudocódigo que fornece a dívida após \(n\) meses. Só temos que tomar cuidado que essa sequência após um número finito de passos passa a ser negativa, caso contrário a dívida não seria paga nunca. Nesse caso, apesar de \(y_n < 0\) a real dívida não existe mais, então a função deve retornar 0. Veja primeiro o pseudocódigo sem usar recursão.
Entrada: n
Saída: yn = dívida após n meses, considerando juros de 1,5% ao mês e valor de empréstimo de R$ 1.000,00.
Nome: Divida
1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0 retorne 1000;
3. Defina y = 1000;
4. Faça i = 1;
5. Faça y = 1.015*y - 200;
6. Incremente i = i + 1;
7. Se i <= n, volte para a linha 5;
6. Se y < 0, retorne 0. Senão, retorne y.Agora veja o pseudocódigo do algoritmo recursivo.
Entrada: n
Saída: yn = dívida após n meses, considerando juros de 1,5% ao mês e valor de empréstimo de R$ 1.000,00.
Nome: Divida_rec
1. Caso n não seja inteiro não negativo, retorne erro.
2. Se n=0 retorne 1000;
3. Faça d = 1.015*Divida_rec(n-1) - 200;
4. Se d<0, retorne 0. Senão, retorne d.Fibonacci
A sequência de Fibonacci é um caso particular de equações de diferenças de segunda ordem, isto é, uma equação em que \(x_n\) depende não só de \(x_{n-1}\) como também de \(x_{n-2}\). Lembrando, uma sequencia de Fibonacci é definida por: \[ \begin{array}{l} F_1 = 1,\\ F_2 = 1, \\ F_n = F_{n-1} + F_{n-2}. \end{array} \]
Vamos escrever um pseudocódigo que recebe como entrada \(n\) e retorna o \(n\)-ésimo termo da sequência de Fibonacci (\(F_n\)). Primeiro sem recursão.
Entrada: n
Saída: \(F_n\) = valor do n-ésimo termo da sequência de Fibonacci.
Nome: Fibonacci
1. Caso n não seja inteiro positivo, retorne erro.
2. Se n=1 ou n=2, retorne 1;
3. Defina F1 = 1 e F2 = 1;
4. Inicie i = 3;
5. Faça Fib = F1 + F2;
6. Faça F1 = Fib e F2 = F1;
7. Incremente i = i + 1;
8. Se i <= n, volte para a linha 5;
9. Retorne Fib.Agora o pseudocódigo do algoritmo recursivo.
Entrada: n
Saída: \(F_n\) = valor do n-ésimo termo da sequência de Fibonacci.
Nome: Fibonacci_rec
1. Caso n não seja inteiro positivo, retorne erro.
2. Se n=1 ou n=2, retorne 1;
3. Retorne Fibonacci_rec(n-1) + Fibonacci_rec(n-2);Veja que nesse exemplo, por se tratar de uma equação de diferenças de segunda ordem, a chamada recursiva é feita duas vezes: Fibonacci(n-1) e Fibonacci(n-2). Em ambas o argumento foi simplificado. Como temos dois casos básicos, n=1 e n=2, garantimos que para qualquer natural n sempre teremos solução.
Fibonacci_rec = function(n){
if(n<=0 || (n%%1 != 0))
stop("O argumento de entrada tem que ser um inteiro positivo.")
if(n==1 || n==2){
return(1)
}
return(Fibonacci_rec(n-1) + Fibonacci_rec(n-2))
}
Fibonacci_rec(10)## [1] 55