fibonacci.c – Recursividade, iteração e algoritmos

Coelhos, recursividade e iteração

Ofereceram ao Sr. Fibonacci um casal de coelhos, recém-nascidos, de um espécie curiosa: tornam-se férteis ao fim de um mês de vida, concebem logo que possível, têm uma gestação de exactamente um mês, cada ninhada consiste sempre num casalinho de coelhos. Nunca morrem. O Sr. Fibonacci preocupou-se: teria comida que chegue para os coelhos? Pôs-se a calcular a evolução do número de casais de coelhos ao longo do tempo:

1. No mês zero o Sr. Fibonacci vivia feliz, sem qualquer coelho. Mal calculava o seu destino...

2. No primeiro mês há um casal de coelhos inférteis.

3. No segundo mês há um casal de coelhos, já férteis e, claro está, com a coelha no início da gestação de mais um casalinho.

4. No terceiro mês há o casal de coelhos original, fértil, e já no início da gestação de mais um casalinho de coelhos. E há, claro está, um casal recém- nascido e, por isso, infértil. Ou seja, há dois casais de coelhos, um fértil e outro infértil.

5. No quarto mês há os dois casais do mês anterior, já férteis, adicionados de um casal recém-nascido, resultado do acasalamento do único casal fértil do mês anterior. Ou seja, há três casais de coelhos, dois férteis e um infértil.

6. No quinto mês há os três casais do mês anterior, já férteis, adicionados de dois casais recém-nascidos, resultado do acasalamento entre os dois casais férteis do mês anterior. Ou seja, há cinco casais de coelhos, três férteis e dois inférteis.

O Sr. Fibonacci concluiu rapidamente que, a partir do terceiro mês,

• o número de casais férteis num mês é sempre igual ao número total de casais no mês anterior e

• o número total de casais num mês é sempre igual à soma do número total de casais existente no mês anterior com o número de casais recém-nascidos, que é igual ao número de casais férteis no mês anterior e que, por isso, é igual ao número total de casais existentes dois meses antes.

Sendo o número de casais de coelhos no mês , então, desde que , . Quando ou , . Ou seja, esta sucessão pode ser descrita de forma recursiva, ou seja, definindo os termos da sucessão em função de outros termos da mesma sucessão.

O que pretendemos aqui é implementar uma função que receba o mês como argumento e devolva o número de casais existentes nesse mês. Como não fornecemos apenas uma implementação, mas várias, com diferentes eficiências, os nomes dessas funções não poderão ser simplesmente fibonacci(), incluindo no seu nome um sufixo que identifica o tipo de implementação usado. Pode argumentar-se que, sendo a eficiência parte da interface de um módulo, então é razoável usar esses sufixos. No entanto, seria preferível, se o nosso objectivo não fosse o estudo dos algoritmos em si, mas a criação de ferramentas para utilização futura ou para disponibilização a terceiros, usar sufixos que fossem reveladores da eficiência da função, e não da sua implementação.

Antes, porém, de passar às implementações, é preciso dizer que o presente oferecido ao Sr. Fibonacci está realmente envenenado. Com efeito, a sucessão de Fibonacci cresce de forma extremamente rápida. Assim, no mês 120, ou seja, dez anos depois da oferta do casal original, o número de casais a alimentar é exactamente 5 358 359 254 990 966 640 871 840. Este valor é demasiado grande para os int nas nossas máquinas habituais, que têm 32 bits, ou mesmo para os long, com 64 bits nessas mesmas máquinas. Por outro lado, a precisão limitada dos tipos de virgula flutuante pode pôr problemas complicados ao cálculo dos termos da sucessão (já tínhamos dito que dos tipos de vírgula flutuante se foge como diabo da cruz?). O código abaixo recorre ao tipo long, numa tentativa de evitar que se atinjam muito cedo os limites dos inteiros. É uma má solução, no entanto. Uma boa solução passaria pela utilização de um tipo capaz de representar números inteiros de dimensão arbitrária (desde que haja memória para o guardar, bem entendido). A implementação de um tal tipo é um excelente exercício de algoritmos e estruturas de dados, mas não o resolveremos aqui.

Implementação

Como se referiu, usamos long como tipo de devolução das funções de cálculo dos termos da sucessão de Fibonacci. Será que isso adianta muito, em relação à utilização de int? Fazendo algumas experiências, é fácil verificar que, em máquinas em que os int têm 32 bits, ou seja, em máquinas em que o maior valor representável num int é 2 147 483 647, o maior termo da sucessão de Fibonacci representável num int é o termo 46, ou seja, , cujo valor é 1 836 311 903. Isto é, usando int só conseguimos obter valores correctos para os primeiros 47 termos da sucessão. Usando long, é fácil verificar que, em máquinas em que os long têm 64 bits, ou seja, em máquinas em que o maior valor representável num long é 9 223 372 036 854 775 807, o maior termo da sucessão de Fibonacci representável num long é o termo 92, ou seja, , cujo valor é 7 540 113 804 746 346 429. Isto é, usando long só conseguimos obter valores correctos para os primeiros 93 termos da sucessão. Melhor que os 47 se se usasse int, mas ainda assim um valor bem pequeno.

O maior termo calculável usando long, 92, deve ser usado nas pré-condições das funções abaixo. Usar o valor literal nesse código é muito má ideia, pois torna mais difícil a compreensão do código. Afinal, haverá que perceba imediatamente o significado desse valor? Para resolver o problema definimos uma constante para guardar esse valor. Uma vez que esta constante será usada para dimensionar arrays que pretendemos inicializar usando as usuais listas de inicializadores do C, não podemos usar a forma mais óbvia de definir constantes em C, i.e., não podemos usar

const int maximum_term_fitting_a_long = 92;

tendo, pelo contrário de usar uma macro do pré-processador.

Inclusão de ficheiros de cabeçalho

Incluímos os seguintes ficheiros de cabeçalho:

• stdio.h – Para declaração do procedimento printf().

• stdlib.h – Para definição da macro EXIT_SUCCESS.

• time.h – Para definição da função clock() e da macro CLOCKS_PER_SEC.

• assert.h – Para definição da macro assert().

Inclusão de ficheiros de cabeçalho próprios

Incluímos apenas um ficheiro de cabeçalho «não oficial»:

• sequence_of_longs.h – Para declaração do TAD (tipo abstracto de dados) sucessão de long usada para guardar em memória dos termos da sucessão já calculados.

Implementação recursiva «estúpida»

Documentação

A documentação da função é feita no formato do Doxygen, como habitualmente.

Definição

Esta implementação segue a estratégia mais comum das soluções recursivas: decompor o problema em problemas mais simples, resolver esses problemas mais simples usando exactamente a mesma estratégia, recursivamente, e compor as soluções dos subproblemas de modo a obter a solução do problema como um todo. Uma solução recursiva, como esta, precisa de possuir casos de paragem (ou casos especiais), para os quais a solução é imediata, não sendo necessária qualquer decomposição adicional. A definição recursiva da sucessão de Fibonacci aparenta adequar-se bem a esta estratégia:

Em primeiro lugar, verificamos as pré-condições e lidamos com as violações que forem detectadas.

Depois, lidamos com os dois casos especiais da sucessão. Estes casos servem também para garantir que as invocações recursivas desta função acabarão sempre por terminar (em tempo finito).

O caso geral é simplesmente a devolução da soma dos termos anterior da sucessão. Para os obter, invocamos a própria função com os dois valores inteiros anteriores a n. O problema desta implenentação é que se está a reduzir o problema de calcular aos subproblemas de calcular e de calcular , mas estes subproblemas não são independentes! Isso faz com que esta implementação seja muitíssimo ineficiente.

Para compreendemos bem a ineficiência desta implementação, vamos calcular alguns valores interessantes.

Em primeiro lugar, uma revelação: a sucessão de Fibonacci pode ser expressa de forma fechada. «Estamos aqui com tudo isto e a coisa resume-se a uma fórmula fechada?», podem perguntar. Sim. Mas pode haver boas razões para não recorrer a essa fórmula: ela obriga-nos a trabalhar com valores de vírgula flutuante e, por isso, a lidar com as correspondentes limitações de precisão. As nossas implementações, recorrendo a long, são exactas... Podem encontrar informação sobre a sucessão de Fibonacci, e sobre a sua forma fechada, em vários locais. Recomendamos os seguintes:

• F_n no Wolfram|Alpha - O Wolfram|Alpha é um motor de pesquisa com a Wolfram por trás (a mesma que produz o maravilhoso Wolfram|Mathematica) só podia ser excelente. E é-o.

• Fibonacci Number no Wolfram|MathWorld - O Wolfram|MathWorld é uma enciclopédia matemática também com a garantia de qualidade da Wolfram. Outra excelente fonte de informação.

• Fibonacci number na Wikipédia.

A forma fechada da sucessão de Fibonacci é

,

onde

, que é chamado número de ouro, e

.

Outra forma fechada é

,

onde

é a função que resulta no inteiro mais próximo ou arredondamento de , sendo que em caso de empate entre dois inteiros mais próximos se escolhe o inteiro que for par.

Ambas as formas mostram bem o que já tínhamos observado: o crescimento da sucessão de Fibonacci é extremamente rápido. Mais precisamente, o crescimento da sucessão de Fibonacci é exponencial, sendo a base da exponencial o número de ouro e o expoente o número do termo da sucessão.

Vamos agora calcular o número de invocações da função recursive_fibonacci() que ocorrem durante a cálculo de um dado termo da sucessão de Fibonacci, ou seja, durante a execução da função que acabámos de definir quando se lhe passa como argumento esse valor . Chamemos a esse número de invocações .

Em primeiro lugar, é evidente que invocar recursive_fibonacci() com como argumento leva a uma invocação inicial, nomeadamente a que acabámos de referir, com como argumento. Se o valor de for 0 ou 1, então não é realizada qualquer outra invocação. Ou seja, quando ou . Se o valor de for maior que 1, então a função será invocada recursivamente com os valores e como argumento, o que resultará num total de invocações. Ou seja, o número de invocações recursivas da função pode ser expresso também de forma recursiva:

Esta definição é muito parecida com a definição recursiva da própria sucessão de Fibonacci. De facto, é fácil demonstrar que . Ou seja, o número de invocações cresce exponencialmente, tal como a própria sucessão de Fibonacci! Não admira que esta implementação seja absolutamente inaceitável...

Já agora, podemos também calcular o número de somas realizadas. Seja o número de somas realizadas quando se invoca recursive_fibonacci() com o argumento . É fácil ver que, quando é 0 ou 1, a invocação de recursive_fibonacci() resulta em 0 somas. Quando se invoca com maior que 1, realiza-se uma soma dos resultados das invocações recursivas com os valores e como argumento, o que resultará num total de somas. Ou seja, o número de somas realizadas durante a invocação da função pode ser expresso também de forma recursiva:

Esta definição é também muito parecida com a definição recursiva da própria sucessão de Fibonacci. De facto, é fácil demonstrar que . Ou seja, o número de somas cresce exponencialmente, tal como a própria sucessão de Fibonacci! Isto quando uma implementação iterativa trivial precisa de 0 somas para calcular o termo 0 da sucessão e de somas para calcular o termo quando . Mais uma vez, não admira que esta implementação seja absolutamente inaceitável.

A moral desta estória não é que a recursividade seja naturalmente perversa. Não o é. As soluções recursivas podem ser tão eficientes quanto as soluções iterativas. O problema aqui não é a recursividade em si, mas o algoritmo usado.

Implementação recursiva com lookup

Documentação

Definição

Esta implementação evita os cálculos repetidos dos mesmos termos da sucessão de Fibonacci usando uma memória auxiliar. A ideia é calcular cada termo da sucessão uma única vez, guardar o seu valor em memória e, das próximas vezes que o termo for solicitado, usar o valor guardado em memória. Isto implica, naturalmente, que a memória usada persista para além do âmbito restrito de uma execução da função. Ou seja, não podemos de forma nenhuma usar variáveis locais automáticas, pois estas são construídas quando a instrução que as define é executada, e destruídas quando se atinge o final do bloco onde a sua definição se encontra. Em vez de partir daqui para as variáveis globais, cujo tempo de vida abarca todo o tempo de execução do programa, e que são visíveis em todo o programa, preferimos usar variáveis locais estáticas. Estas variáveis definem-se usando o qualificador static, duram desde a execução da instrução que as define até o final do programa e têm a mesma visibilidade restrita que qualquer variável local tem. Note-se que a instrução de definição de qualquer variável local estática é executada uma única vez, nomeadamente a primeira vez que o fluxo de execução do programa passa por essa instrução. A partir daí a instrução de definição, com a respectiva inicialização, é ignorada. Logo, a inicialização de uma variável local estática é feita uma única vez durante a execução do programa.

Uma vez que o número de termos da sucessão de Fibonacci calculáveis através desta função é limitado, dado que ela devolve valores long, só se podendo calcular o valor dos termos entre 0 e MAXIMUM_TERM_FITTING_A_LONG, podemos reservar espaço para todos os termos num array F de long. A utilização de uma macro MAXIMUM_TERM_FITTING_A_LONG na expressão para cálculo do comprimento do array permite-nos usar inicializadores do C. Dessa forma, podemos inicializar a memória dos termos da sucessão de Fibonacci com os dois primeiros termos dessa sucessão, que têm os valores 0 e 1, respectivamente, correspondentes aos termos com índices 0 e 1.

Não basta definir o espaço de memória dos termos da sucessão: é necessário definir uma variável que guarde em cada instante quantos termos estão já calculados. Neste caso inicializa-se a variável com o valor 2, uma vez que se inicializou a memória com os dois primeiros termos da sucessão de Fibonacci.

Estamos agora preparados para indagar o valor do termo da sucessão de Fibonacci solicitado. Se o termo já constar na memória de termos calculados, i.e., se o valor n for inferior a number_of_calculated_terms limitamo-nos a devolver o valor memorizado.

O caso geral passa por

1. invocar recursivamente a própria função para obter os termos n - 2 e n - 1,

2. calcular o termo n como soma dos dois termos anteriores calculados,

3. guardar esse novo termo na memória, de modo a não precisar de ser recalculado, e

4. terminar a função, devolvendo o valor do novo termo ao retornar ao ponto de invocação da função.

Estes passos estão condensados em apenas duas linhas de código. Essa condensação seria considerada uma má prática em quase todas as linguagens de programação, mas este tipo de código é idiomático em C, pelo que preferimos apresentá-lo desta forma. Seja como for, uma forma ortodoxa de escrever este código seria:

F[n] = recursive_fibonacci(n - 2) + recursive_fibonacci(n - 1);
number_of_calculated_terms++;

return F[n];

Alternativamente, podemos considerar que o caso especial é aquele em que o termo pretendido não foi ainda calculado, o que nos levaria ao seguinte código, bem mais legível, que substitui não apenas as duas últimas linhas do código apresentado, mas também as duas anteriores:

if (number_of_calculated_terms <= n) {
        F[n] = recursive_fibonacci(n - 2) +
               recursive_fibonacci(n - 1);
        number_of_calculated_terms++;
}

return F[n];

Implementação recursiva com lookup usando TAD

Documentação

Definição

Em vez de se usar um array de long como memória para os termos já calculados da sucessão de Fibonacci, bem como um inteiro indicando a quantidade de termos memorizados, recorremos aqui ao TAD sucessão de long, representado pela estrutura struct sequence_of_longs. No caso particular da sequência se Fibonacci, a utilização deste TAD não traz grandes vantagens face à utilização de um array, dada a pequena quantidade de termos da sucessão representáveis no tipo long. No entanto, é um bom exercício recorrer aqui ao TAD, exercício que nos pode ser útil noutros casos em que o dimensionamento a priori do array não seja tão fácil.

Tal como definido o TAD, o código cliente só pode trabalhar com as sucessões através de ponteiros. Assim, precisamos de definir uma variável local estática (de modo a que o seu valor persiste entre invocações da função recursive_fibonacci_using_ADT). Dadas as restrições do C, não podemos usar o construtor SEQL_new() directamente na inicialização, que tem de ser feita usando uma expressão constante. Assim, optámos por inicializar o ponteiro F com o valor especial NULL.

Dada a inicialização do ponteiro com NULL, podemos agora detectar o seu valor inicial NULL para lhe atribuir o endereço de uma nova estrutura struct sequence_of_longs construída de forma dinâmica através do construtor SEQL_new(). Este código é executado sempre que a função é invocada, o que é uma infelicidade, mas não há forma de o evitar, dado que não é possível inicializar o ponteiro F para a sucessão de long com o valor devolvido pela função SEQL_new().

Outro problema associado às limitações do C é o da libertação de memória. O C não fornece nenhum mecanismo para executar código no contexto das variáveis locais estáticas no final do programa de modo a podermos «arrumar a casa», ou seja, libertar recursos que lhes estejam associados. Neste caso os recursos são apenas duas variáveis dinâmicas: (a) a struct sequence_of_long apontada por F e, embora como clientes não o devêssemos precisar de o saber, (b) o array dinâmico usado internamente pelo TAD para guardar os termos. Como toda a memória dinâmica associada ao programa em execução é libertada durante a sua terminação, a nossa violação do princípio de que quem reserva memória explicitamente a deve também libertar explicitamente não é dramática.

Se o termo já constar na sucessão de long contendo os termos da sucessão de Fibonacci já calculados, então limitamo-nos a devolvê-lo.

Se o termo não está ainda calculado, há que fazê-lo. Uma vez que, depois de o calcular, teremos de o adicionar à memória e devolver, definimos uma variável F_n para guardar o valor calculado. Uma vez que o valor usado para inicializar esta variável depende do valor de n, usamos o operador ?: do C para discriminar entre as três diferentes formas de inicialização, evitando ter de recorrer a uma definição sem inicialização seguida de duas instruções de selecção encadeadas:

long F_n;
if (n == 0)
        F_n = 0L;
else if (n == 1)
        F_n = 1L;
else
        F_n = recursive_fibonacci_using_ADT(n - 2) +
              recursive_fibonacci_using_ADT(n - 1);

Agora que já temos o valor de F_n calculado, devemos guardá-lo em memória, na nossa sucessão de long, de modo a não precisar de ser calculado de novo.

Finalmente, devolvemos o valor calculado.

Implementação recursiva eficiente sem memória

Esta implementação recursiva dispensa a utilização de memória auxiliar e tem uma eficiência semelhante à da implementação iterativa. No entanto, requer a definição de uma função auxiliar. Assim, serão definidas duas funções:

• tail_recursive_fibonacci() – Função com ligação (linkage) externa, i.e., visível em outros ficheiros de implementação que componham o programa, que tem uma interface idêntica à das restantes funções para cálculo de termos da sucessão de Fibonacci definidas até agora.

• tr_fibonacci() – Função com ligação interna, i.e., invisível noutros ficheiros de implementação que componham o programa, e que corresponde à implementação recursiva do cálculo de termos da sucessão de Fibonacci. A razão para a utilização de um função auxiliar prende-se com o facto de esta possuir dois parâmetros adicionais, previous_value e value, que não são relevantes para os clientes do código. Assim, a função tail_recursive_fibonacci() limitar-se-á a invocar esta função, passando-lhe os argumentos apropriados, devolvendo o valor que ela por sua vez devolver.

Declaração da função auxiliar

O especificador static usado nesta declaração, e na correspondente definição que se encontra mais abaixo, tem como objectivo alterar a ligação desta função de externa (que é a ligação por omissão) para interna.

Documentação

Definição

A função com ligação externa serve apenas para lidar com o caso especial da invocação com argumento nulo e para invocar a função auxiliar com os argumentos apropriados. Estes argumentos correspondem aos valores iniciais da sucessão de Fibonacci. A função auxiliar usará os parâmetros correspondentes para ir acumulando os termos da sucessão, como se verá.

Começamos por lidar com o caso especial correspondente ao termo 0 da sucessão.

Finalmente, devolvemos o valor devolvido pela invocação da função auxiliar tr_fibonacci(), passando-lhe como argumentos o número n do termo a calcular da sucessão de Fibonacci e os valores dos dois primeiros termos da sucessão de Fibonacci.

Definição da função auxiliar

Esta função calcula de forma recursiva o termo da sucessão de Fibonacci, desde que . Para que isso aconteça, no entanto, a invocação inicial da função deve ser feita não apenas com o primeiro argumento , mas também com segundo e terceiro argumentos 0 e 1, respectivamente, ou seja, tr_fibonacci(, 0, 1). Estes argumentos são usados para inicializar os parâmetros correspondentes, ou seja, n, previous_value e value. Essa invocação inicial dará origem a outras invocações recursivas da mesma função, pelo que ocorrerá uma sequência de execuções da função. Podemos identificar cada uma dessas execuções pelo seu número de ordem, a que podemos chamar . A primeira execução corresponde a , a segunda a e assim sucessivamente. Iremos demonstrar que, numa dada execução , é sempre verdadeira a seguinte proposição acerca dos valores dos parâmetros da função:

• n = ,

• previous_value = e

• value = .

A demonstração desta proposição faz-se por indução matemática.

Quando , os valores dos parâmetros correspondem aos argumentos passados na invocação inicial, que por hipótese são respectivamente , 0 e 1. Substituindo esses valores nas igualdades acima e fazendo nelas também , chegamos a

• = , ou seja, = ,

• 0 = , ou seja, 0 = e

• 1 = ,

que é obviamente uma proposição verdadeira, dada a definição da sucessão de Fibonacci.

Seja uma execução resultante da invocação recursiva da função realizada durante a execução . Admitamos que a proposição é verdadeira para , ou seja, que

• n = ,

• previous_value = e

• value = .

Será que também o é para a execução ? Os argumentos passados à função na invocação recursiva que ocorre durante a execução da função são, por ordem,

• n - 1 = = ,

• value = = e

• previous_value + value = = (pela definição da sucessão de Fibonacci).

Conclui-se assim facilmente que, durante a execução , os valores dos parâmetros são

• n = ,

• previous_value = e

• value = ,

pelo que a proposição também é verdadeira durante a execução .

Também é fácil ver que o número de execuções da função decorrentes da invocação inicial com argumentos (com ), 0 e 1 é exactamente . Assim, a última execução, durante a qual o caso especial n == 1 é atingido, corresponde a , e por isso o valor devolvido pela instrução return é value = , tal como pretendido. Esse valor é depois sucessivamente devolvido pelas execuções intermédias da função, inclusivamente pela invocação inicial. Logo, tr_fibonacci(, 0, 1) = .

Implementação iterativa

Documentação

Definição

Começamos primeiro por lidar com os casos especiais da sucessão.

Recorremos a duas variáveis que guardam, em cada passo do ciclo, o valor do termo anterior e o valor corrente da sucessão.

O ciclo é executado n - 2 vezes, uma vez que os valores iniciais das variáveis acima correspondem aos termos 1 e 2 da sucessão.

O novo termo corrente, correspondente a i + 1, é obtido pela soma do termo corrente, correspondente a i, com o termo anterior, correspondente a i - 1.

Neste momento temos apenas disponíveis os termos i + 1 e i - 1. Precisamos de obter o novo termo anterior, ou seja, o termo i, que perdemos devido à atribuição anterior! Podemos recuperá-lo obtendo a diferença entre o termo i + 1 e o termo i - 1. Note-se que este truque requer uma subtracção adicional por cada iteração do ciclo! Podíamos facilmente evitar essa operação se tivéssemos usado uma variável auxiliar.

Finalmente, devolvemos o termo corrente.

Obtenção de estimativas para o tempo de execução das funções

Definimos agora um procedimento que realiza experiências para estimar o tempo de execução de uma qualquer das várias funções de cálculo de termos da sucessão de Fibonacci que desenvolvemos.

Documentação

Definição

Calculamos o número mínimo de clocks do relógio a passar durante as repetições das execuções da função em teste para perfazer um tempo mínimo de 0,1 segundos. Dessa forma garantimos um mínimo de precisão nas medidas sem, com isso, se realizar um número excessivo de repetições (não queremos esperar muito...). A macro CLOCKS_PER_SEC representa o número (inteiro) de clocks ou tiques do relógio que ocorrem num segundo. O tipo clock_t é um sinónimo de um dos tipos inteiros sem sinal do C (o tipo exacto depende da implementação).

Imprimimos o título da experiência em curso.

A variável previous_time guardará o tempo de execução estimado da função para o valor anterior de n. Dessa forma podermos calcular o aumento percentual do tempo de execução com o aumento em uma unidade do número do termo da sucessão de Fibonacci em cálculo.

Ciclo de repetição de experiências para números crescentes do termo da sucessão a calcular. Note que os tempos de execução estimados para as implementações recursivas com memória são afectados por dois factos: (a) já se calcularam os termos com números inferiores, que por isso estão memorizados, e (b) após a primeira repetição, o próprio termo em experiência fica memorizado... Analise os tempos obtidos tendo estes factos em conta.

Este primeiro ciclo serve para calcular o número de repetições necessário para se acumular o tempo mínimo de 0.1 segundos.

Uma vez que o tempo de execução do ciclo anterior foi afectado pelo próprio tempo de execução da função clock(), executamos de novo as repetições para obtermos as estimativas do tempo de execução da função de cálculo da sucessão de Fibonacci excluindo o tempo de execução da função clock().

Estimamos o tempo de execução da função de cálculo da sucessão de Fibonacci dividindo o tempo total de execução do ciclo pelo seu número de iterações (repetitions). O tempo de execução do ciclo em segundos é calculado dividindo o número total de clocks ou tiques do relógio decorridos entre o início e o fim do ciclo pelo número de tiques por segundo.

Imprimimos o valor do termo da sucessão calculado bem como a estimativa do tempo necessário para efectuar esse cálculo. Se não se tratar do primeiro termo da sucessão, imprimimos também a variação percentual desse tempo face ao necessário para o cálculo do termo anterior.

Guardamos o tempo estimado como tempo anterior a usar na próxima iteração do ciclo.

Programa principal

Definimos uma constante que guarda o número do maior termo da sucessão de Fibonacci que será usado nas experiências realizadas com a função que usa o algoritmo recursivo estúpido. Sem este cuidado, o nosso programa não terminaria em tempo útil.

Realizamos experiências com cada uma das funções, para obter estimativas do seu tempo de execução.

Finalmente, usamos cada uma das funções para obter os termos da sucessão, podendo assim mais facilmente confirmar que os cálculos estão a ser realizados correctamente.