Using threads and recursion in Java to calculate Fibonacci numbers

I'm relatively new in the Java world and I have a problem which I don't understand.

I have a Class (to get the fibonacci row):

class Fib {
    public static int f(int x){
     if ( x < 2 )
      return 1;  
     else 
      return f(x-1)+ f(x-2);   
    }
}

The task now is to start f(x-1) and f(x-2) each in a separate Thread. One time with implementing the Thread class and the other with implementing Runnable. As you probably know, it's an exercise from my prof.

I know how to start a Thread in Java and I know how this whole Thread thing theoretically works, but I can't find a solution for starting separate Threads in this recursive function.

What has to be done in the run function?

Probably

public void run(){
//int foo=start f(this.x-1)
    //int bar=start f(this.x-2)  
    //return foo+bar?
}

And how can I paste x in my runnable function? Is x passed into the object at creation?

Class Fib ...{
  int x;
  public ... run ... 
  public ... f(x)....

}

in the main method

(new Fib(x)).start();

Or am I on a totally wrong path?

From stackoverflow

• For this to work, you need 1) a way to pass the number into the new thread, 2) to start the thread, 3) to wait for the thread to finish, and 4) a way to get the result back from the thread.

  You can pass in the number through the constructor. You can have a public data member called "answer" to contain the result of the computation. Starting the thread can be done with the start() method, and the join() method waits for the thread to complete.

  The following example demonstrates this. That should be a good starting point; from here you can abstract away some of the messiness to get a better API as desired.

  public class Fib extends Thread
  {
      private int x;
      public int answer;
  
      public Fib(int x) {
          this.x = x;
      }
  
      public void run() {
          if( x <= 2 )
              answer = 1;
          else {
              try {
                  Fib f1 = new Fib(x-1);
                  Fib f2 = new Fib(x-2);
                  f1.start();
                  f2.start();
                  f1.join();
                  f2.join();
                  answer = f1.answer + f2.answer;
              }
              catch(InterruptedException ex) { }
          }
      }
  
      public static void main(String[] args)
          throws Exception
      {
          try {
              Fib f = new Fib( Integer.parseInt(args[0]) );
              f.start();
              f.join();
              System.out.println(f.answer);
          }
          catch(Exception e) {
              System.out.println("usage: java Fib NUMBER");
          }
      }
  }
  

  evildead : thank you very much, this helps me a lot to understand how it all work together

  Peter Lawrey : Wow, that is impressively inefficient. The number of thread created grows exponentially as n increases. I would never of thought of doing that. However, there is some risk you will hang the machine before you can stop your process.

  Outlaw Programmer : Ideally you would be working out of a fixed-size thread pool or something, but those concepts would probably just complicate the answer. This is probably the simplest possible solution to the OP's problem, so +1 for that.

  Eli Courtwright : I agree that you would never actually want to implement something this way; this was merely the simplest working test program to accomplish the approach asked for by the question. Threads aren't really a good approach for this kind of problem, but this is a still decent teaching problem.

  evildead : as I wrote on a comment down below, this is the exact answer of my exercise. The task was to see how threading and Java worked. Another task is to do a procedural algorithm, wich is much more effizient and so we are teached that threading is not always the best Method :)

• You've got the right idea about starting threads in the fib function, and about passing x to the object through the constructor; you'll also need to have a way to get the result of the calculation out of the object at the end - I'm sure you can figure that out ;-) The thread-starting procedure you use in fib is just the same way you always start a thread, like (new Fib(x-1)).start() although you might want to save the thread in a variable because you'll need it to get the result of the computation later.

  evildead : thank you too, i think the post above shows me how to handle threads much better now.

• Using threads is usually intended to improve performance. However each thread adds an overhead and if the task performed is small, there can be much more over head than actual work done. Additionally most PCs can only handle about 1000 threads and will hang if you have much more than 10K threads.

  In your case, fib(20) will generate 6765 threads, fib(30) creates 832K, fib(40) creates 102M threads, fib(50) creates over 12 trillion. I hope you can see this is not scalable.

  However, using a different approach you can calculate fib(1000000) in under one minute.

  import java.math.BigInteger;
  
  /*
  250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
  Time to compute: 3.466557 seconds.
  1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
  Time to compute: 58.1 seconds.
  */
  public class Main {
      public static void main(String... args) {
          int place = args.length > 0 ? Integer.parseInt(args[0]) : 250 * 1000;
          long start = System.nanoTime();
          BigInteger fibNumber = fib(place);
          long time = System.nanoTime() - start;
  
          System.out.println(place + "th fib # is: " + fibNumber);
          System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
      }
  
      private static BigInteger fib(int place) {
          BigInteger a = new BigInteger("0");
          BigInteger b = new BigInteger("1");
          while (place-- > 1) {
              BigInteger t = b;
              b = a.add(b);
              a = t;
          }
          return b;
      }
  }
  

  Michael Myers : Apparently, using threads is part of the assignment, though. Maybe the input is extremely restricted or something.

  Outlaw Programmer : I think the assignment is to teach the fork+join pattern.

  evildead : well, thank you for solving another part of my homework :) My Lecture is called something like distributed Programming with a focus on threading, paralellism. The task was too implement runnable, using the Thread class and to do a procedural algorithm with sharing and storing data between threads.

  Peter Lawrey : From this exercise you could "learn" that threads are slow and you are better of not using them. I am not sure this is the right conclusion. An assignment where using thread actually helped would be better.

• So with the help of you all I managed to do the same thing with implementing runnable instead of using the Thread Class.

  Can you all have a look and tell me if thats the way how to do it if the task is to implement runnable. The Code itself works.

  public class Fib implements Runnable
  {
  private int x;
  public  int answer;
  
  public Fib(int x) {
      this.x = x;
  }
  
  public void run() {
      if( x < 2 )
          answer = 1;
      else {
          try {
              Fib f1= new Fib(x-1);
              Fib f2= new Fib(x-2);
              Thread threadf1=new Thread(f1);
              Thread threadf2=new Thread(f2);
              threadf1.start();
              threadf2.start();
              threadf1.join();
              threadf2.join();
  
              answer = f1.answer + f2.answer;
  
          }
          catch(InterruptedException ex) { }
      }
  }
  
  public static void main(String[] args)
  
  {
      try {
  
           for (int i=0;i<19;i++){
               Fib f= new Fib(i);
               Thread threadf= new Thread(f);
               threadf.start();
               threadf.join();
  
               System.out.println("Ergebnis:"+f.answer);
  
              }
          }
  
      catch(Exception e) {
          System.out.println("usage: java Fib NUMBER");
      }
    }
  }