Why recursive function must return 1 by default

Question

1.16/5 (4 votes)

See more:

I have the following recursive function:

C#

public int Fibonacci(int number)
      {
          if (number == 0)
              return 0;
          else if (number == 1)
              return 1;
          else
          {
              return Fibonacci(number - 2) + Fibonacci(number - 1);
          }

      }

My questions are:

why the function returns 0 if i return 0 in the else condition,
why the function returns the value multiplied by 2 if I return 2 in the else condition.
So the test scenario will be:

Fibonacci(5) // when (else return 0) | Result: 0
Fibonacci(5) // when (else return 1) | Result: 5 // Correct
Fibonacci(5) // when (else return 2) | Result: 10

I don't understand why, and when the multiplication is happening.

Any explanation?

What I have tried:

C#

public int Fibonacci(int number)
      {
          if (number == 0)
              return 0;
          else if (number == 1)
              return 1;
          else
          {
              return Fibonacci(number - 2) + Fibonacci(number - 1);
          }

      }

Posted 26-Feb-16 4:21am

Keymayker

Updated 26-Feb-16 5:40am

v3

Add a Solution

Comments

Jochen Arndt 26-Feb-16 10:50am

There is no multiplication. It happens by the recursive call and adding the results for F(n-1) and F(n-2).

However, your code is not a valid Fibonacci implementation. F(5) is 5 and not 13. See https://en.wikipedia.org/wiki/Fibonacci_number.

Keymayker 26-Feb-16 10:58am

Okey i implemented correct Fibonacci implementation, but again i have the same issue, and question

Jochen Arndt 26-Feb-16 11:29am

What issue?
By definition F(0) = 0, F(1) = 1, and F(2) = 1.
Why would you want to return anything else?
You can do so, off course, but then it won't be Fibonacci.

2 solutions

Solution 2

0 and 1 provide a way for your recursive method to end: if the tests weren't there then it would just keep on calling itself until it ran out of stack space and crashed!
Think about what it does, and try running it in the debugger. Pit a breakpoint on the first call to the method, and step into it, and watch exactly what happens as you step through. You'll soon start to see what's happening, and why the two tests are essential!

Posted 26-Feb-16 5:14am

OriginalGriff

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)

Patrice T · Accepted Answer · 2016-02-26T05:40:00

This is not your code!
So first thing to do is to read a reference about the Fibonacci sequence Fibonacci number - Wikipedia, the free encyclopedia[^].

Quote:
why the function returns 0 if i return 0

This is part of the definition F0= 0

Quote:
in the else condition,
why the function returns the value multiplied by 2 if I return 2 in the else condition.

Jumping from 1 to 2 is not necessary a multiplication. read source code more carefully.

Quote:
So the test scenario will be:

Fibonacci(5) // when (else return 0) | Result: 0
Fibonacci(5) // when (else return 1) | Result: 5 // Correct
Fibonacci(5) // when (else return 2) | Result: 10

No!
Check the reference to get the right answers.

Quote:
I don't understand why, and when the multiplication is happening.

Any explanation?

Because there is no multiplication!
Read again the source code.

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]