import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author Peter Cappello
 */
public class Recursion 
{
    /**
     * Computes the nth Fibonacci number in a doubly recursive manner.
     * This merely illustrates a recursively defined method; 
     * these numbers can be computed more efficiently.
     * @param n the Fibonacci number to compute
     * @return the nth Fibonacci number.
     */
    static long fib( int n )
    {
        return n < 2 ? n : fib( n - 1 ) + fib( n - 2 );
    }
    
    /**
     * Recursively computers the binomial coefficient n choose j:
     * The number of subsets of size j taken from of a set of n elements.
     * This merely illustrates a recursively defined method; 
     * these numbers can be computed more efficiently.
     * @param n The size of the set.
     * @param j the size of the subsets.
     * @return the binomial coefficient.
     */
    static long nChooseJ( int n, int j )
    {
        return j == 0 || n == j ? 1 : nChooseJ( n - 1, j - 1 ) + nChooseJ( n - 1, j );
    }
    
    /**
     * Recursively computers the binomial coefficient n choose j:
     * The number of subsets of size j taken from of a set of n elements.
     * @param n The size of the set.
     * @param j the size of the subsets.
     * @return the binomial coefficient.
     */
    static long binaryCoefficient( int n, int j )
    {
        return j == 0 || n == j ? 1 : n * binaryCoefficient( n - 1, j - 1 ) / j;
    }
    
    public static void main( String[] args )
    {
        for ( int i = 0; i < 10; i++ )
        {
            System.out.println("fib( " + i + " ): " + fib( i ) );
        }
        
        for ( int j = 0, n = 10; j <= n; j++ )
        {
            System.out.println("nChooseJ( " + n + ", " + j + " ): " + nChooseJ( n, j ) + "\t binaryCoeffieient: " + binaryCoefficient( n, j) );
        }
    }
}