Esta aula introduz o conceito de recursividade.
Na aula anterior fizemos uma função que permite calcular o factorial de um número. O modo como programamos a função reflecte de maneira explicita os sucessivos produtos que temos de fazer para calcular o factorial de um número n. A ideia base é fazer um ciclo que varre os números de 1 a n e ter uma variável auxiliar p para acumular os sucessivos produtos. O código é assim,
#include <stdio.h>
/* calcula o factorial de n. Assume que n>=0 */
int factorial( int n )
{
int i,p;
p = 1;
for( i=2; i<=n; i++ )
p = p * i;
return p;
}
Este problema também pode ser resolvido de maneira recursiva. Recordem-se que o factorial de um número n pode ser definido como n! = 1 x 2 x 3 x ... x n, mas também pode ser definido recursivamente (ou por recorrência) através das seguintes duas regras:
Neste caso, definimos a função factorial em termos da própria função factorial. Este é o conceito fundamental da recursividade. Trata-se de uma maneira especial de resolver problemas em que a ideia chave é resolver o problema em termos de uma instância mais pequena do próprio problema. A dimensão do problema vai sendo sucessivamente reduzida e eventualmente atinge-se um caso base em que a recursividade pára.
Em C, a função factorial recursiva ficaria assim,
/* calcula o factorial de n. Assume que n>=0 */
int factorial( int n )
{
if( n==0 )
return 1;
else
return n * factorial(n-1);
}
O modo como está programado é uma tradução directa das duas regras que definem o factorial. A primeira é o caso base, a segunda é o caso recursivo.
Para melhor se perceber o modo como a função funciona, é útil vermos o modo como a computação é executada internamente no computador. No caso da função ser definida de modo não recursivo, é necessário duas variáveis, i e p para armazenar o estado da computação. Por exemplo, ao calcular o factorial de 6, o computador vai passar sucessivamente pelos seguintes estados:
i p
=== ===
1
2 2
3 6
4 24
5 120
6 720
No caso recursivo nada disto acontece. Para calcular o factorial de 6, o computador tem de calcular primeiro o factorial de 5 e só depois é que faz a multiplicação de 6 pelo resultado (120). Por sua vez, para calcular o factorial de 5, vai ter de calcular o factorial de 4. E por aí fora até esbarrar no caso base.
Resumindo, aquilo que acontece internamente é uma expansão seguida de uma contracção:
factorial(6)
6 * factorial(5)
6 * 5 * factorial(4)
6 * 5 * 4 * factorial(3)
6 * 5 * 4 * 3 * factorial(2)
6 * 5 * 4 * 3 * 2 * factorial(1)
6 * 5 * 4 * 3 * 2 * 1 * factorial(0)
6 * 5 * 4 * 3 * 2 * 1 * 1
6 * 5 * 4 * 3 * 2 * 1
6 * 5 * 4 * 3 * 2
6 * 5 * 4 * 6
6 * 5 * 24
6 * 120
720
Um dos exercícios da aula prática 5 foi sobre números de Fibonacci. Os números de Fibonacci são definidos da seguinte forma. O primeiro número é 1. O segundo também é 1. O n-ésimo número é definido como sendo a soma dos dois números anteriores.
fib(1) = 1 fib(2) = 1 fib(n) = fib(n-1) + fib(n-2), para n > 2
Na referida aula prática fizeram um programa que calculava esta sequência de números. Na altura ainda não tinham aprendido funções, e muitos de vós devem ter programado o exercício de forma iterativa (isto é, não recursiva).
Imaginem que vos pedia para programarem uma função que calcule o n-ésimo número de Fibonacci. Uma solução possível é fazerem-no de forma iterativa, tal e qual como fizeram na aula prática 5. Uma outra alternativa é programarem a função de modo recursivo. A implementação é trivial e é novamente uma tradução directa da definição dos números de Fibonacci. Aqui vai o código:
/* calcula o n-ésimo número de Fibonacci. */
int fib( int n )
{
if( n==1 || n==2 )
return 1;
else
return fib(n-1) + fib(n-2);
}
Esta solução é muito mais simples de programar do que a versão iterativa. Contudo, esta versão é muitíssimo ineficiente. A razão é simples. Cada vez que a função fib é chamada, a dimensão do problema reduz-se apenas de uma unidade (de n para n-1), mas são feitas duas chamadas recursivas. Isto dá origem a uma explosão combinatorial e o computador acaba por ter de calcular a mesma coisa várias vezes.
Para melhor se perceber, vejamos o que acontece internamente no computador quando chamamos a função como o valor 5.
Para calcular fib(5) temos de calcular fib(4) e fib(3). Por sua vez, para calcular fib(4) temos de calcular fib(3) e fib(2). E por aí fora. Este tipo de processamento é ineficiente porque obrigamos o computador a fazer trabalho desnecessário. No exemplo concreto, para calcular fib(5) temos de calcular fib(4) 1 vez, fib(3) 2 vezes, fib(2) 3 vezes, fib(1) 5 vezes, e fib(0) 3 vezes. Numa implementação iterativa (como fizeram na aula prática 5), apenas era necessário calcular fib(5), fib(4), fib(3), fib(2), fib(1), e fib(0) 1 vez.
Para calcular o quinto número de Fibonacci até nem é um grande problema, mas para números maiores torna-se muito ineficiente. Experimentem calcular os primeiros 50 números de Fibonacci utilizando o método iterativo e o método recursivo. Vão ver que a resposta é imediata no primeiro caso, mas poderá levar uma hora no caso da implementação recursiva!
Pelo que foi exposto, pode parecer que é de evitar a programação de modo recursivo. De facto, em quase todas os casos existe uma implementação iterativa que é mais eficiente. Contudo, existe muitas implementação recursivas que são igualmente eficientes. Além disso, em muitos casos a implementação recursiva é muito mais simples. Ao longo de outras disciplinas, nomeadamente PED e Algoritmos, poderão aprofundar mais este tópico.
Pensar de modo recursivo exige um certo poder de abstracção, sendo uma ferramenta fundamental para os programadores. Nesta secção, vou ilustrar mais três exemplos que requerem que pensemos de modo recursivo.
A definição da sintaxe de algumas instruções da linguagem C são definidas recursivamente. Por exemplo, vimos que a definição sintáctica da instrução while é definida à custa do próprio conceito de instrução.
while( expressão )
instrução
Por outras palavras, uma instrução while pode ser definida como a palavra while seguido de um parêntesis a abrir, seguido de uma expressão, seguido de um parêntesis a fechar, seguido de uma instrução (a qual pode ser uma nova instrução while). Ou seja, estamos a definir uma instrução à custa do próprio conceito de instrução.
Neste caso também existe um caso base (o equivalente ao n=0 no exemplo da função factorial) que consiste nas instruções mais simples da linguagem (instruções de atribuição, printf's, etc...).
Considerem o conceito de antepassado. O meu bisavô ou a minha tetravó são meus antepassados. Um antepassado é alguém que é pai do pai do pai, ou mãe do pai da mãe da mãe, e por aí fora. Aparentemente, trata-se de um conceito de difícil definição. Contudo, se pensarmos de forma recursiva podemos defini-lo facilmente utilizando apenas os conceitos de pai e mãe:
No secundário devem ter aprendido 2 maneiras distintas de representar conjuntos: (1) por extensão, e (2) por compreensão. O primeiro método trata-se de uma simples enumeração de todos os elementos do conjunto. Por exemplo, o conjunto A pode ser definido em extensão do seguinte modo:
A = {1,2,3,4}
mas também pode ser definido em compreensão como sendo o Conjunto de números Naturais inferiores a 5. Formalmente:
A = {x pertencente N: x<5}
Os conjuntos também podem ser definidos por indução. Por exemplo, considerem a seguinte definição para um conjunto hipotético chamado D:
Estas 3 regras definem o conjunto D de maneira indutiva. Trata-se de um conceito que é muito parecido com o conceito de recursividade, visto que estamos a definir D à custa dele próprio. Já agora, que conjunto D é este que estamos a falar?