Fibonnaci Number

Java 3.12.2010 2 Comments

By definition, the first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two.

Fibonacci, Wikipedia

Generating Fibonacci numbers is an assignment often given to Java students when they are being introduced to recursion.

Recursion is programming technique that involves a method calling itself to solve a problem. When implementing a recursive solution we look for two things:

  • A base case that returns a value without any subsequent recursive calls.
  • A reduction step that relates the methods inputs to other inputs that converge oto the base case.

It is worth mentioning that using recursion to generate Fibonacci numbers is actually quite inefficient, and is really only useful as a learning exercise.

package com.learnjava.math;

/**
 * Write a Java program that generates the 
 * first 10 Fibonacci numbers using recursion..
 * 
 * @author http://learn-java-by-example.com
 *
 */

public class Fibonacci {

	/**
	 * Retuens fibonacci number for n
	 * @param n
	 * @return fibonacci number for n
	 */
	public static int fibonacci(int n) {
		if (n<=1) {
			
			// By definition, the first two Fibonacci numbers are 0 and 1
			// This is our base case
			
			return n;
		
		} else {
			
			// and each subsequent number is the sum of the previous two
			// Remember that Java passes parameters by value, this
			// means this method uses a local copy of n
			
			return fibonacci(n-1) + fibonacci(n-2);
		}
	}

	public static void main(String[] args) {
		
		for (int n = 0; n<10; n++) {
			int fibonacci = fibonacci(n);
			System.out.print(fibonacci+", ");
		}
		System.out.println("...");
	}

}

2 Responses to “Fibonnaci Number”

  1. Dinesh

    How would you do Fibonacci without recursion?

Leave a Reply

s2Member®