Simulation of a Function

Question

0.00/5 (No votes)

See more:

int fib(n) {
 if(n == 0)
   return 0
 if(n == 1)
   return 1
 return fib(n-1)+fib(n-2) }

Simulate fib(5)
~~This was my interview question. I don't know what the real answer is ! Can you help me by answering this question ?~~

Posted 29-Mar-11 10:14am

UL UL ALBAB

Updated 29-Mar-11 10:34am

Hans Dietrich

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 29-Mar-11 16:38pm

Nothing is "simulated" here. This is just a regular recursive functions with two bugs. Please see my Answer for a fix.
--SA

Sergey Alexandrovich Kryukov 29-Mar-11 16:39pm

Or, I see you fixed "=" to "==".
Now, fix (n-2) and it will work.
--SA

Sergey Alexandrovich Kryukov 29-Mar-11 16:40pm

Already fixed. Now it should work.
--SA

Sergey Alexandrovich Kryukov 29-Mar-11 16:42pm

No, not fixed yet. Also, add ";" after each statement.
--SA

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Manfred Rudolf Bihy · Accepted Answer · 2011-03-29T10:24:00

Solution 1

fib(5) =                 fib(4)                +              fib(3)
           fib(3)          +       fib(2)            fib(2)    +    fib(1)
   fib(2)    +    fib(1)      fib(1)  +  fib(0)  fib(1) + fib(0)
fib(1) + fib(0)

All you have to do is substitution until the recursion terminating conditions are hit:

fib(1) == 1 and fib(0) == 0 so the result is: 5

Cheers,

Posted 29-Mar-11 10:24am

Manfred Rudolf Bihy

Comments

UL UL ALBAB 29-Mar-11 16:28pm

Cheers...

UL UL ALBAB 29-Mar-11 16:28pm

Thank you so much...

Sergey Alexandrovich Kryukov 29-Mar-11 16:37pm

Manfred, I really fail to understand how this can make sense. And how about fib(2)? The OP's code will work correctly after fixing of just two bugs.
Please see my Answer.
--SA

Manfred Rudolf Bihy 29-Mar-11 16:42pm

Please see my comment on your answer :)

Sergey Alexandrovich Kryukov 29-Mar-11 16:46pm

Now I see. "Simulate...". Hm...

Anyway, this part of question is scratched, and marked C++ and had 3 bugs in terms of C++, so... I don't think I put it absolutely wrong.

It least, I understand you Answer. Thank you for the explanation.
--SA

Manfred Rudolf Bihy 29-Mar-11 16:49pm

No problem, SA!

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-03-29T10:35:00

Solution 2

Please pay attention: this is C++. "=" means assignment, not the check for being equal. To check is two objects are equal, use "==".

Another bug is this: if n == 1, fib(n - 2) is fib(-1), which you don't want. Hence, you need three branches: for n == 0, 1 more (in the last case, use else; this is the only case when n-2 is valid.

Also, add ';' after each statement.

I thing, if you fix just these two bugs, you code will work.
Don't you consider more general case where first to members are arbitrary "seed value"? Then you need to modify the code.

Note: OP fixed the code in Question after I posted this.

—SA

Posted 29-Mar-11 10:35am

Sergey Alexandrovich Kryukov

Updated 29-Mar-11 10:43am

v4

Comments

Manfred Rudolf Bihy 29-Mar-11 16:42pm

SA, this is not your day I guess. OP was asked in an interview to simulate the execution of that function. That's all there is to it. :)

All I did is show OP how to use substitution to solve that.

Why he tagged it C++ is beyond me though. Maybe it was the job he applied for.

Sergey Alexandrovich Kryukov 29-Mar-11 16:44pm

Maybe. How the function can be simulated if it has 3 bugs?
Thank you for the note.
--SA

Manfred Rudolf Bihy 29-Mar-11 16:46pm

It is pseudo code or more probably written down from memory if the interview question really had a C++ function in it.

Sergey Alexandrovich Kryukov 29-Mar-11 16:49pm

But you did not "simulate" the pseudo-code. You "simulated" correct Fibonacci. So the original code (before OP fixed it), did not what your code did. So my corrections still make sense.
--SA

Manfred Rudolf Bihy 29-Mar-11 16:48pm

And it is possible to simulate the execution on paper. That the function is syntactically challenged doesn't change a thing here.

Sergey Alexandrovich Kryukov 29-Mar-11 16:50pm

Oh yes, paper or not, does not matter.
As I just say, it was not syntactically challenged, but had a bug with N-2. That's why my correction was correct.
--SA

Manfred Rudolf Bihy 30-Mar-11 2:42am

"Syntactically challenged" means exactly that. OMG