Lucas.java

import java.util.LinkedList;
public class Lucas {
  public static int lucas(int n){
    switch(n){
      case 0:
        return 2;
      case 1:
        return 1;
      default:
        if (n < 0)
          throw new IllegalArgumentException();
        return lucas(n-1)+lucas(n-2);

    }
  }
  public static void doi(int n){
    System.out.println(""+n+": "+lucas(n) );
  }
  public static LinkedList<Integer> linkedluckas(int n){
    final LinkedList<Integer> l = new LinkedList<>();
    for(int i =0; i < n; i++)
      l.add(lucas(i));
    return l;
  }

  public static LinkedList<Integer> linkyluke(int n){
    final LinkedList<Integer> l = new LinkedList<>();

    if (n <= 0)
      throw new IllegalArgumentException();

    int x_minus_1=0, x_minus_2=0, x;
    for(int i =0; i < n; i++){
      switch(i){
        case 0:
          x=2;
          break;
        case 1:
          x=1;
          break;
        default:
          x=x_minus_1+x_minus_2;
      }
      l.add(x);
      x_minus_2=x_minus_1;
      x_minus_1=x;
    }
    return l;
  }

  public static LinkedList<Integer> linkedlucasrecusivesingleargument(int n ){
    final LinkedList<Integer> l = new LinkedList<>();
    int x;
    switch(n){
      case 0:
        l.add(2);
        break;
      case 1:
        l.add(2);
        l.add(1);
        break;
      default: // n is >= 2
        final LinkedList<Integer> l2 = linkedlucasrecusivesingleargument(n-1);
        l.addAll(l2);
        int num_elements = l.size();
        l.add(l.getLast() + l.get(num_elements-2));
        // if we had a custom linkedlist implementation we could make this faster
        // Node last = l.getLastNode();
        // l.add( last.value + last.previous.value );
    }
    return l;
  }

  public static void main(String[] a){
    doi(0);
    doi(1);
    doi(2);
    doi(3);
    doi(4);

    System.out.println(linkedluckas(10));

    System.out.println(linkyluke(30));
    System.out.println(linkedlucasrecusivesingleargument(30));
  }
}