 |
|
Você está aqui: Delphi ::: Dicas & Truques ::: Recursão (Recursividade) |
Obtendo o número ou a sequencia de Fibonacci recursivamente usando DelphiQuantidade de visualizações: 18710 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): ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
// 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;
begin
// vamos calcular o fibonacci de 6
res := fibonacci(6);
// vamos mostrar o resultado
ShowMessage('O Fibonacci de 6 é: ' + IntToStr(res));
end;
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: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
// 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;
begin
// vamos calcular o fibonacci de 6 e registrar
// a cadeia de chamadas em um TMemo
res := fibonacci(6, Memo1);
// vamos mostrar o resultado
ShowMessage('O Fibonacci de 6 é: ' + IntToStr(res));
end;
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: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
// 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;
res: String;
begin
res := '';
for i := 0 to 9 do
begin
res := res + IntToStr(fibonacci(i)) + ' ';
end;
ShowMessage(res);
end;
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 |
