Fibonacci Using Recursioin

Algorithms
, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int Fibo(int n){
   if(n<=1)
       return n;
   else
       return Fibo(n-2) + Fibo(n-1);
}

int main(int argc, const char * argv[]) {
    for(int i=0;i<10;i++)
        F[i] = -1;
    printf("%d\n", Fibo(5));
    return 0;
}

Using memorisation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int F[10];
int Fibo(int n){
    if (n<=1) {
        F[n] = n;
        return F[n];
    } else {
        if(F[n-2] == -1)
            F[n-2] = Fibo(n-2);
        if(F[n-1] == -1)
            F[n-1] = Fibo(n-1);
        return F[n-2] + F[n-1];
    }
}
int main(int argc, const char * argv[]) {
    for(int i=0;i<10;i++)
        F[i] = -1;
    printf("%d\n", Fibo(5));
    return 0;
}