fibonacci calculation

[XodoX]

I'm trying to code something that's a little complex, imo.

It's a C++ program that will count the number of operations of recursive functions and will compare it with O(g(n)). This count value will basically estimate time complexity function T(n). You have to find the g(n) to get O(g(n)) that acts as upper bound. The program takes as input n, some positive integer and choosing between a recursive or non-recursive version, It's gonna evaluate two recursive functions:

f(n)=f(n-1)+f(n-1), f(1)=1

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2); starting at fibonacci(1)=1 and fibonacci(2)=1

The code will have to produce one line of output per function at some n value showing:
result, operation count (T(n)) and worst-case time complexity with your estimated O(g(n)) exhibiting c and some n0, according to the definition (n0 greater or equal than 2). It must find some c value so that the inequality always
holds (the tigther the better).

And the output - it needs produce n rows with 7 columns, varying n from 1 to the n value given as parameter.
In each row values are separated with spaces. The first column is n and then there are three columns per recursive function, showing partial result, T(n) and O(g(n)). Numbers should appear right aligned.

It's gonna look like this:

[IMG]http://img13.imageshack.us/img13/3115/outputto.png[/IMG]

I am not getting it. Can someone please tell me how to get started here? The hardest part for me here is developing the recursive and non recursive function that will calculate it.:S

[Taywin]

The hardest part is to find a way to implement it in non-recursive (iterative) unless you already know what to do.

OK, when you implement a recursive, you always have to figure out what the "base case" is. A recursive function always tests for the value that cannot be used to call itself again. In this case, I believe it is 1 and 2. If a passing in value is 1 or 2, it will return 1. Now, what you need to do is to create a function and receive a value which is the fib that you want to find. Some thing like... fib(int n). In side the function, if you see that "n" is equal to 1 or 2, then you return 1. The part for recursive is after that. It means if it is not 1 or 2, you need to call itself passing values that is supposed to be as in your fib function above. You just return it.

So all of this in recursive would be about 2 lines of codes in the function if you condense the if statements. For iterative, it will be more...

[XodoX]

Well, I only have to do two functions, correct? The f(n)=f(n-1)+f(n-1), f(1)=1 and the
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2); starting at fibonacci(1)=1 fibonacci(2)=1. I'm not quite understanding how this fibonacci works. But that's basically what it is - a code that solves it? I hate recursive functions :(

[Taywin]

Correct. You need to do 2 functions - iterative and recursive. For recursive, the construction of it is difficult to understand at first. Once you understand it, you will see that it is a lot more intuitive than iterative approach.

Let's see a simple recursive function here...

[1] int factorial(int n) {
[2]   if (n<2) {
[3]     return 1;
      }
[5]   return (n*factorial(n-1));
    }

OK, you know that line 1 is what you declare for calling a function (name & argument). Look at line 2, it is the condition check for base case. It means that a function must have at least 1 condition that will break the loop. For factorial, the base case is when a number is 0! or 1! which would be equal to 1. I use "<" just in case the "n" value is negative which will cause an infinite loop. My decision is to return 1 regardless.

If the line 2 condition is satisfied - the value n is less than 2 - it will return 1 to the caller and stops that function call.

If the line 2 condition is NOT satisfied, it will skip and go to line 5.

At line 5, it will return a value which comes from calling itself (recursive call) using a number which is less than itself by 1. Whatever value returns from the function will be multiplied with the original incoming value.

Now let's see how it works for calling factorial(4)...

/*
factorial(4);

calling #1:
Line 1 is being called as factorial(4)
Line 2 is being executed  4<2 ?
  It is not satisfied, skip
Line 5 is being executed
  the execution is as...
  return (4 * factorial(3));
  the value 4 will be pushed and saved somewhere in the stack

calling #2:
Line 1 is being called as factorial(3)
Line 2 is being executed  3<2 ?
  It is not satisfied, skip
Line 5 is being executed
  the execution is as...
  return (3 * factorial(2));
  the value 3 will be pushed and saved somewhere in the stack

calling #3:
Line 1 is being called as factorial(2)
Line 2 is being executed  2<2 ?
  It is not satisfied, skip
Line 5 is being executed
  the execution is as...
  return (2 * factorial(1));
  the value 2 will be pushed and saved somewhere in the stack

calling #4:
Line 1 is being called as factorial(1)
Line 2 is being executed  1<2 ?
  Yes, return 1

Time to pop everything from the stack...
Back to line 5 of calling #3
  return (2 * (1));  <-- return value of 1 from calling #4
Back to line 5 of calling #2
  return (3 * (2));  <-- return value of 2 from calling #3
Back to line 5 of calling #1
  return (4 * (6));  <-- return value of 6 from calling #2

returned value from calling #1 is 24.
*/

See how easy and very simple of a recursive function? If you write it in iterative approach, the code is longer and need more variables.

So for fib function, it works very similar. What you need to figure out is the base cases & how to return the call if all base cases are not satisfied (skipped).

[XodoX]

Thank you. I don't remember Fibonacci that well, but isn't this just a regular fib equation ? The input n will come from the user, so I basically just have to work with that, then.
But how does the T(n) O(g(n)) etc. work. Do you know? I'm not really sure what they want there. Estimate the complexity function?

[Taywin]

The fib is used in advanced math. The value of it grows very fast too. The input n comes from a user, yes. If I remember correctly, once n value is 21 or higher, the value grows bigger than "int" can hold.

What you talk about T(n), you are talking about time complexity analysis of the function. When you talk about O(..), you are talking about time complexity. There is another symbol called "big omega" which is similar to big "O" but it is the upper bound. There is a method to compute T(n) for a recursive function. I can't remember the detail though. Then you could convert T(n) to O(...).

[XodoX]

The fib is used in advanced math. The value of it grows very fast too. The input n comes from a user, yes. If I remember correctly, once n value is 21 or higher, the value grows bigger than "int" can hold.

What you talk about T(n), you are talking about time complexity analysis of the function. When you talk about O(..), you are talking about time complexity. There is another symbol called "big omega" which is similar to big "O" but it is the upper bound. There is a method to compute T(n) for a recursive function. I can't remember the detail though. Then you could convert T(n) to O(...).

Ok, I'm not quite getting it. I guess I should worry first about the two equations given huh. Once I have those I guess it's not that hard to add the other stuff to "count" whatever needs to be counted.
Yes, it's supposed to be double not int.