Aula 16: Programação recursiva

Recursivo

Um procedimento é recursivo se está definido em termos de si própria

Exemplo 1: Factorial

O exemplo clássico é o cálculo do factorial n! Uma solução seria fazer isto com um ciclo, tal como está presentado nas aulas 11 e 12:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
var result: integer;
    i: integer;
begin
result := 1;        (* initialize the variable *)
for i := 1 to n do
    result := i*result;
Factorial := result; (* return result *)
end;
De facto, esta função, retorna o factorial do argumento, por exemplo Factorial(5) = 120. Verifica isto!

Mais elegante é uma solução que usa recursividade. Vamos escrever uma função que está definida em termos de si própria, ou seja chama si própria, tal como nós aprendemos na escola,

n! = n*(n-1)!

Vamos fazer exactamento isso:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
(* the value to be returned is expressed in terms of itself: *)
Factorial := n*Factorial(n-1);
end;

Esta função já está quase correcta. O único problema é que ... nunca vai acabar. Por exemplo, se nós chamamos a função com Factorial(4), a função tentará calcular 4*Factorial(3) e, por isso, vai chamar Factorial(3). Factorial(3) tentará calcular 3*Factorial(2), o que implica chamar Factorial(2), ... que vai chamar Factorial(1) ... que vai chamar Factorial(0) ... que vai chamar Factorial(-1) ... que vai chamar Factorial(-2) ... e isto nunca vai acabar. A função nunca vai retornar nada e o computador vai crasher, provavelmente com o erro "stack overflow". Obviamento temos de incluir uma maneira de parar o ciclo recursivo. Agora, lembra que em matemática tivemos também uma condição de parar, para o Factorial este semente foi a definição

1! = 1

Vamos incluir a mesma coisa na nossa função:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
if n=1 then
Factorial := 1
else
Factorial := n*Factorial(n-1);
end;

A idea nós podemos extrair deste exemplo é que sempre precisa de incluir uma maneira de acabar chamar a função recursiva. Tal como nos ciclos repeat-until e while-do temos de dar a possibilidade de sair dos cálculos. Senão o programa nunca vai acabar.

Exemplo 2: Fibonacci

Lembra das aulas práticas, a definição dos números Fibonacci é também dado em termos de si própria:
f_n = f_n_-2 + f_n_-1
Com as condições de parar (os sementes)
f₁ = 1
f₂ = 1
Por exemplo:
f₃ = 1 + 1 = 2
f₄ = 1 + 2 = 3
f₅ = 2 + 3 = 5
f₆ = 3 + 5 = 8
f₇ = 5 + 8 = 13

Podemos implementar isto numa função recursiva. Nota a condição de parar:
FUNCTION Fibonacci(n: integer): integer;
begin
if (n=1) OR (n=2) then
Fibonacci := 1
else
Fibonacci := Fibonacci(n-2) + Fibonacci(n-1);
end;

Variáveis

Variáveis declaradas dentro de um procedimento recursivo são todas variáveis locais. Além disso, cada vez o procedimento será chamado, uma nova versão ou cópia (em inglês: instance), ou "caixa" da variável será creada o que existe até o procedimento acabará. Cada versão, embora de ter o mesmo nome, fica num endereço diferente na memória, ou seja são caixas diferentes. Como exemplo, vamos introduzir uma variável na nossa função Factorial:
FUNCTION Factorial(n: integer): integer;
Var m: integer;
begin
m := 2*n;
if n=1 then
Factorial := 1
else
Factorial := n*Factorial(n-1);
WriteLn(m);
end;
Se vamos chamar esta função com argumento 3 a seguinte vai acontecer:

Factorial(3) é chamada
    uma variável com nome m é criada
    2*3 é atribuido a este m
    Factorial(2) é chamada
      uma variável com nome m é criada (diferente do que o m acima!)
      2*2 é atribuido a este m
      Factorial(1) é chamada
        uma variável com nome m é criada (diferente do que os m acima)
        2*1 é atribuido a este m
        ... chega a condição de parar e Fortorial retorna 1;
        O procedimento mostra o valor de m: 2
      saí da Factorial(1)
      O procedimento mostra o valor de m: 4
    saí da Factorial(2)
    O procedimento mostra o valor de m: 6
saí da Factorial(3)

O que nós podemos aprender aqui é que a variável m não é um objecto estático na memória, sempre no mesmo endereço, mas sim a variável será criada cada vez que o procedimento será chamado. Existem quantas versões da variável igual ao nível de profundidade de chamar a função. Além disso, só a última versão pode ser usada na função. Só temos acesso à última versão (até o momento que este nível de chamar a função acebará).
(em C é possivel impedir a criação das novas versões da variável; se nós sempre queremos usar a mesma "caixa" podemos por a palavra "static" em frente da declaração da variável)

Mini Teste

Para testar o seu conhecimento, sobre o que aprendeu nesta aula, clique aqui para um teste on-line.

Peter Stallinga. Universidade do Algarve, 7 Abril 2002