by BehindJava

How to use threads and recursion in Java to print Fibonacci numbers

Home » java » How to use threads and recursion in Java to print Fibonacci numbers

This is a quick tutorial on using threads and recursion in Java to print 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.
  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 .... 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;
    }
}