/* Fibonacci-Folge
   für Sun-Java
   Wolfgang.Urban@schule.at
*/

class Fibonacci {
        
        // Hauptprogramm

        public static void main(String args[]) {
                System.out.println("Alg. 1 : "+fibo1(10));
                System.out.println("Alg. 4 : "+fibo4(10,1,1));
        }
        
        // Algorithnus 1

        static long fibo1(int n) {
                if (n<=2) return 1;
                else return fibo1(n-1)+fibo1(n-2);
        }
                
        // Algorithnus 1a

        static long fibo1a(int n) {
                if (n<=2) return 1;
                return fibo1a(n-1)+fibo1a(n-2);
        }

        // Algorithnus 3
        // a,b und neu müssen im Voraus Werte erhalten (if)!
    
        static long fibo3(int n) {
                long a=1, b=1, neu=0;
                
                if (n<=2) return 1;
                for (int zaehler=3; zaehler<=n; zaehler++) {
                        neu = a+b;
                        a = b;
                        b = neu;
                }
                return neu;
        }
        
        // Algorithnus 4

        static long fibo4(int n, int a, int b) {
                if (n==1) return a;
                if (n==2) return b;
                return fibo4(n-1,b,a+b);
        }
                        
}