 |
|
||||
Você está aqui: Delphi ::: Dicas & Truques ::: Recursão (Recursividade) |
Obtendo o número ou a sequencia de Fibonacci recursivamente usando DelphiQuantidade de visualizações: 18419 vezes |
|
Uma sequencia de números de Fibonacci é definida como a seguir: Fib(n) = n | se n < 2 Fib(n) = Fib(n - 2) + Fib(n - 1) | caso contrário A definição estabelece que, se os primeiros dois números são 0 e 1, então qualquer número na sequencia é a soma de seus dois predecessores. Mas esses predecessores são, por sua vez, somas de seus predecessores, e assim por diante, até o início da sequencia. Desta forma, a sequencia produzida pela definição é: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377... Se quisermos, por exemplo, calcular o Fibonacci de 6, teríamos apenas que somar seus dois predecessores, a saber, 3 e 5, resultando em 8. Mas antes, é preciso calcular o Fibonacci de 3 e também de 5. É aqui que o uso da recursão ou recursividade nos auxilia bastante. Veja uma função fibonacci() recursiva que calcula o Fibonacci de 6. Note a condição de parada da cadeia de chamadas (que deve ocorrer quando n for menor que 2):
// função recursiva para calcular o Fibonacci
// de um determinado número
function fibonacci(n: Integer): Integer;
begin
if n < 2 then
Result := n
else
Result := fibonacci(n - 2) + fibonacci(n - 1);
end;
// vamos chamar a função recursiva
// a partir do Click de um botão
procedure TForm1.Button1Click(Sender: TObject);
var
res: Integer;Execute o código e veja o resultado. Mas, tenha cuidado ao tentar obter o Fibonacci de um número muito grande devido à recursividade excessiva. Isso ocorre porque, para calcular Fibonacci(6) nós precisamos calcular Fibonacci(5), Fibonacci(4), Fibonacci(3), Fibonacci(2), Fibonacci(1) e Fibonacci(0) primeiro. No entanto, para calcular Fibonacci(4), temos que novamente calcular Fibonacci(3), Fibonacci(2), Fibonacci(1) e Fibonacci(0) novamente. Veja no trecho de código a seguir como podemos obter uma lista de todas as chamadas:
// função recursiva para calcular o Fibonacci
// de um determinado número
function fibonacci(n: Integer; memo: TMemo): Integer;
begin
// vamos registar esta chamada
memo.Lines.Add('Fibonacci(' + IntToStr(n) + ')');
if n < 2 then
Result := n
else
Result := fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
end;
// vamos chamar a função recursiva
// a partir do Click de um botão
procedure TForm1.Button1Click(Sender: TObject);
var
res: Integer;Execute o código e verá a seguinte árvore de chamadas: Fibonacci(6) Fibonacci(4) Fibonacci(2) Fibonacci(0) Fibonacci(1) Fibonacci(3) Fibonacci(1) Fibonacci(2) Fibonacci(0) Fibonacci(1) Fibonacci(5) Fibonacci(3) Fibonacci(1) Fibonacci(2) Fibonacci(0) Fibonacci(1) Fibonacci(4) Fibonacci(2) Fibonacci(0) Fibonacci(1) Fibonacci(3) Fibonacci(1) Fibonacci(2) Fibonacci(0) Fibonacci(1) De fato é uma cadeia de chamadas muito grande para calcularmos apenas o Fibonacci de 6. Se precisássemos calcular o Fibonacci de 200, o número de chamadas chegaria à casa dos milhões. Não tente! Pode haver estouro da pilha do sistema operacional. Podemos combinar a função recursiva que vimos no início da dica com um laço for para obter os 10 primeiros termos da sequencia de Fibonacci. Veja:
// função recursiva para calcular o Fibonacci
// de um determinado número
function fibonacci(n: Integer): Integer;
begin
if n < 2 then
Result := n
else
Result := fibonacci(n - 2) + fibonacci(n - 1);
end;
// vamos chamar a função recursiva para calcular
// os 10 primeiros termos da sequencia de Fibonacci
procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;Para fins de compatibilidade, esta dica foi escrita usando Delphi 2009. |
 Link para compartilhar na Internet ou com seus amigos: |
Desafios, Exercícios e Algoritmos Resolvidos de Delphi |
Veja mais Dicas e truques de Delphi |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
