[Algorithm] About Fibonacci sequence

 ----------------------------------------------------------------------

Hello, i am GameDeveloperPlayground.

I am a Korean student and I post it for English practise.

I would appreciate pointing out grammar or typos.

----------------------------------------------------------------------

In this post, about Fibonacci sequence.

Fibonacci sequence

Fibonacci sequence is that adds the previous two numbers to create the number of current positions.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

Except for the start two numbers 0 and 1, summarize the total number of previous number and previous number at previous number atfer the third.

0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...

There are a number of ways to implement such a simple algorithm.

Fibonacci sequence implementation using recursive function call.

int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Algorithm(n - 1) + Algorithm(n - 2);
}

The first and second values are set to 0 and 1, respectively returning 0 and 1, and returning the sum of the previous of n and the previous of the previous of n.

have just completed implementation, but every time enter the Algorithm function need to check wgether n is 1 or 2.

have implemented it as a loop this time to remove the fuplicate test twice.

int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
    {
        int beforevalue = 0;
        int current = 1;
 
        for(int i=1; i<n; ++i)
        {
            int temp = current;
            current += beforevalue;
            beforevalue = temp;
        }
        return current;
    }
}

Changed the part that calls tell recursive function to thefor statement.

Current is the current number, and befroevalue is the previous number.

The next number is the current number plus the previous number. so you can add current and before value.

Other ways to do it...  Similar in performance, but there is another ' tail recursion' implementation. in code.

int Algorithm(int n){
    return AlgorithmTail(n, 0, 1);
}
 
int AlgorithmTail(int n, int before, int next){
    if (n == 0)
        return before;
    else
        return AlgorithmTail(n - 1, next, before + next);
}

After one hour

Before is next

Next is before + next.

So iterates through the tail recursion function and returns the current value (before) if the value of n is zero.

We will discuss the tail recursive function in detail in another post.

Thank you.