Nesta aula vamos comparar o algoritmo de Fibonacci RECURSIVO e ITERATIVO e comparar o tempo de execução de cada um. Como vimos nas aulas anteriores, é extremamente simples resolver alguns problemas com recursão. Contudo, será que sempre devemos utilizar algoritmos recursivos?

A recursão é uma feramente fantástica na computação, porém deve ser usada com cautela, como veremos na aula de hoje. Caso você não tenha feito a aula 158: Por que não devo usar Fibonacci recursivo? Sugiro que faça ela primeiro pois ajudará a entender a diferença de tempo entre as duas versões.

Código em C para o fibonacci recursivo e iterativo

Execute o código a seguir em sua máquina e observe a diferença de tempo entre as duas versões. Quanto maior for n, a função iterativa não sofrerá um grande acréscimo de tempo. Contudo, a função recursiva se tornará muito mais lenta. O motivo foi explicado em detalhes na aula 158.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
        Aula 165: Calcular o tempo de execução do algoritmo de FIBONACCI recursivo e iterativo.

        Escrito por Wagner Gaspar
        Março de 2021
*/
/*
        Função recursiva para calcular um termo n da sequência de fibonacci
        Como a sequência cresce muito rápido, está sendo usado o operador long para que o tipo int ocupe 8 bytes.
*/
long long int fiboR(int n){
    if(n == 1)
        return 0;
    else{
        if(n == 2)
            return 1;
        else
            return fiboR(n - 1) + fiboR(n - 2);
    }
}

/*
        Função iterativa para calcular um termo n da sequência de fibonacci
        Como a sequência cresce muito rápido, está sendo usado o operador long para que o tipo int ocupe 8 bytes.
*/
long long int fiboI(int n){
    long long int a = 0, b = 1, c;
    int i = 2;
    if(n == 1)
        return a;
    else{
        if(n == 2)
            return b;
        else{
            while(i < n){
                c = a + b;
                a = b;
                b = c;
                i++;
            }
            return c;
        }
    }
}

int main () {

    int n = 50;
    time_t tIni, tFim;

    tIni = time(NULL); // obtem a hora do computador
    printf("Fibonacci iterativo: %lld\n", fiboI(n));
    tFim = time(NULL);
    printf("\tTempo em segundos: %f\n\n", difftime(tFim, tIni)); // diferença entre a hora de início e a hora de fim

    tIni = time(NULL);
    printf("Fibonacci recursivo: %lld\n", fiboR(n));
    tFim = time(NULL);
    printf("\tTempo em segundos: %f\n\n", difftime(tFim, tIni));

    return 0;
}