Aula 16: Programação Recursiva
Traduzido por Ana Paula Costa

Recursividade

Uma função é recursiva se é definida em termos de si mesma (i.e.,se se chama a si própria)

Exemplo 1: Factorial

O exemplo clássico é o cálculo da função factorial n! Nós podemos implementar a função com um ciclo, tal como foi descrito nas aulas 11 e 12:
int factorial(int n)
 /* returns n! */
{
  int i, result;

  result = 1;        /* initialize the variable */
  for (i=1; i<=n; i++)
    result = i*result;
  return(result);
}
Esta função de facto irá retornar o factorial do argumento, por exemplo factorial(5) = 120.

Uma solução muito mais interessante é através da definição da função factorial em termos de si mesma, tal como aprendemos na escola,

  n! = n*(n-1)!

Vamos fazer exactamente isso:
int factorial(int n)
 /* should return n! */
{
    /* the value to be returned is expressed in terms of itself: */
  factorial = n*factorial(n-1);
}
 
Esta função está quase correcta. O único problema é que nunca irá parar de se chamar a si própria. Por exemplo, podemos chamá-la com factorial(4), que irá depois tentar calcular 4*factorial(3) e assim chamar factorial(3). factorial(3) irá tentar calcular 3*factorial(2), que irá chamar factorial(2), ... que irá chamar factorial(1) ... que irá chamar factorial(0) ... que irá chamar factorial(-1) ... que irá chamar factorial(-2) ... e por aí fora. O programa nunca irá retornar nada e o computador irá encravar, gerando provavelmente um erro do tipo "stack overflow". Claramente, temos que construir a função de forma a que em determinada altura ela páre de se chamar a si própria. Relembrar que na forma matemática de definir uma função em termos de si mesma temos sempre que incluir uma forma de paragem, para a função factorial é

 1! = 1

Vamos colocar a forma de paragem na nossa função:
int factorial(int n)
 /* returns n! */
{
  if (n==1)
    return(1);
  else
    return(n*Factorial(n-1));
}

A ideia que importa reter é que se deve incluir na função a possibilidade de ela obter um resultado e terminar o cálculo recursivo. Tal como temos que dar a um ciclo a possibilidade de terminar, temos que dar essa possibilidade também às funções recursivas. Caso contrário, o programa continuará para sempre (ou irá encravar).

Exemplo 2: Fibonacci

Recordando as aulas práticas, a definição do número de Fibonacci é feita em termos de si mesmo:
  fn = fn-2 + fn-1
com as condições de paragem
  f1 = 1
  f2 = 1
Por exemplo,
  f3 = 1 + 1 = 2
  f4 = 1 + 2 = 3
  f5 = 2 + 3 = 5
  f6 = 3 + 5 = 8
  f7 = 5 + 8 = 13

Podemos implementar isto numa função, reparar na condição de paragem:
int fibonacci(int n)
{
  if ((n==1) || (n==2))
    return(1);
  else
    return(fibonacci(n-2) + fibonacci(n-1));
}

Variáveis

As variáveis que são declaradas dentro de funções recursivas são todas locais. Mais ainda, sempre que a função é chamada, uma nova instância da variável é criada e existe até que a função termine. (Em C podemos prevenir esta situação com a palavra "static" antes da declaração de variáveis). Cada uma destas variáveis, embora tenham o mesmo nome, irão apontar para um espaço diferente na memória. Para exemplificar, vamos criar uma variável local na nossa função factorial:
int factorial(int n)
{
  int m, result;

  m = 2*n;
  printf("%d ", m);
  if (n==1) then
    result = 1;
  else
    result = n*factorial(n-1);
  printf("%d ", m);
  return(result);
}
Quando chamamos a função com argumento 3, irá acontecer o seguinte:
 
instrução
variáveis
factorial(3) é chamada  
  são criadas as variáveis n, m e result m=* r=* n=*
  3 é atribuído a n (da chamada da função)
  2*3 é atribuído a m		 m=6 r=* n=3
  factorial(2) é chamada m=6 r=* n=3
    são criadas as variáveis n, m e result
          (novas; diferentes das anteriores!)		 m=* r=* n=* m=6 r=* n=3
    2 é atribuído a n (da chamada da função)
    2*2 é atribuído a m		 m=4 r=* n=2 m=6 r=* n=3
    factorial(1) é chamada m=4 r=* n=2 m=6 r=* n=3
      são criadas as variáveis n, m e result 
          (diferentes das de cima)		 m=* r=* n=* m=4 r=* n=2 m=6 r=* n=3
      1 é atribuído a n (da chamada da função)
      2*1 é atribuído a m		 m=2 r=* n=1 m=4 r=* n=2 m=6 r=* n=3
      ... chegámos à condição de paragem e result = 1; m=2 r=1 n=1 m=4 r=* n=2 m=6 r=* n=3
      é escrito o valor de m: 2 m=2 r=1 n=1 m=4 r=* n=2 m=6 r=* n=3
      o valor de result (1) é retornado para a instrução de chamada
      factorial(1) termina, os últimos n, m e result são destruídos		 m=4 r=* n=2 m=6 r=* n=3
    result é calculado: n*factorial(n-1) fica
    n*'valor retornado' -> 2*1 = 2		 m=4 r=2 n=2 m=6 r=* n=3
    é escrito o valor de m: 4 m=4 r=2 n=2 m=6 r=* n=3
    o valor de result (2) é retornado para a instrução de chamada
      factorial(2) termina, os últimos n, m e result são destruídos		 m=6 r=* n=3
  result é calculado: n*factorial(n-1) fica
  n*'valor retornado' -> 3*2 = 6		 m=6 r=6 n=3
  é escrito o valor de m: 6 m=6 r=6 n=3
  o valor de result (6) é retornado para a instrução de chamada
      factorial(3) termina, os últimos n, m e result são destruídos		  
o valor retornado por factorial(3) é 6  

r significa variável 'result'
* significa valor indeterminado
O que aprendemos daqui é que as variáveis não são objectos estáticos na memória, que apontam para certos endereços, mas em vez disso, as variáveis são criadas na altura em que corremos o programa. Cada vez que entramos na função, novas variáveis são criadas e irão existir até que se saia da função. Mais ainda, como se pode ver no exemplo em cima, as últimas variáveis criadas são as usadas localmente.
(Isto aplica-se apenas a linguagens que têm variáveis dinâmicas, como o C ou PASCAL).

Teste Rápido:
Para testar os conhecimentos sobre o que aprendeu nesta aula, prima aqui para fazer um teste on-line. De notar que este Não é o formato que será utilizado no teste final!
Peter Stallinga. Universidade do Algarve, 22 November 2002