Using threads and recursion in Java to calculate Fibonacci numbers

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");        }    }}

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 .... 10243516470957309231046875Time to compute: 3.466557 seconds.1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875Time 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;    }}

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.