1

I am trying to learn Dynamic Programming and one of the examples they give in Wikipedia of what is not Dynamic Programming, is a recursive way of getting Fibonacci sequence up to certain number. I.E.

Given a recursive function, say:

fib(n) = 0 if n = 0
         1 if n = 1
         fib(n - 1) + fib(n - 2) if n >= 2

We can easily write this recursively from its mathematic form as:

function fib(n)
  if(n == 0 || n == 1)
    n
  else
    fib(n-1) + fib(n-2)

But I cannot get the pseudo code to work.

when I do this method in Java, I get an error the operator + is undefined for methods void:

 public void fib(int n) {

     if (n == 0 || n == 1) {

         System.out.println(n);
     } else
         return fib(n - 1) + fib(n - 2);

 }
8
  • 1
    Your sudo code suggests System.out.println(n); should actually be return n Dec 12, 2013 at 15:35
  • 1
    @RossDrew I use the upgraded sudo code, it's guaranteed to give the correct-answer(TM) Dec 12, 2013 at 15:40
  • @RichardTingle Sudo code, now that is boss Dec 12, 2013 at 15:43
  • 1
    @RossDrew This program operates as coded; could there be any better definition of correct? Dec 12, 2013 at 15:47
  • 1
    @RossDrew "guaranteed" ;-);-) Dec 12, 2013 at 15:49

4 Answers 4

8

in the line with return fib(n - 1) + fib(n - 2), you add the return values of the fib() function. So you should actually return a (int) value, even if n==0||n==1.

 public int fib(int n) {

     if (n == 0 || n == 1) {
         return n;
     }
     else {
         return fib(n - 1) + fib(n - 2);
     }
 }

you then call and print you result from outside the function:

System.out.println(fib(42));
4

It has no return type so you can't mathematically add it to anything, let alone itself.

public void fib(int n)  //returning void

Give it a return type

public int fib(int n) //yey \o/
1

Try this.

public class Test
{
public static int fib( int n )
{
    if ( n == 0 || n == 1 )
        return n;
    else
        return fib( n - 1 ) + fib( n - 2 );
}

public static void main( String[] args )
{
    System.out.println(fib( 6 ));
}
}
2
  • 2
    there is nothing to explain in this. The code snippet by Eduardo Dennis clearly depicts that the method do not return anything but still in else statement this method is called using return and + operator. Definitely will get a compilation error. Dec 12, 2013 at 15:45
  • 2
    ^ that was an explanation :P
    – Ross Drew
    Dec 12, 2013 at 15:46
1

Just change return type of fib function to int. and in function change

if (n == 0 || n == 1){return n; }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.