хочу разобраться с рекурсией

[Pawel]

Доброго времени суток!
Сделал программу генерации чисел Фибоначчи с помощью рекурсии, и она их генерирует, но перед этим выводит всякие промежуточные данные.
Вот, собственно, код:

public class Fibon {
    public int fib(int n) {
    	int f;
    	if (n <= 0) {
    	    f = 0;  		
    	} else if (n == 1 || n == 2) {
    	    f = 1;    			    	
	} else {	    	
	    f = fib(n - 2) + fib(n - 1);	    		
	}
	System.out.print(f + " ");	    
	return f;    		
    }
    
    public static void main(String[] args) {
        new Fibon().fib(5);
    }
}

А вот результат: 1 1 2 1 1 1 2 3 5
Хотя должно быть только 1 1 2 3 5
Я так понимаю, лишний вывод происходит из-за того, что в методе 2 раза используется рекурсия, но не представляю, как это исправить.
Пожалуйста, помогите разобраться!

Вычитал, что для устранения повторных вычислений надо применить рекурсию с запоминанием. Возможно, кто-нибудь подскажет, как это сделать и что это вообще такое?

[Pawel]

Спасибо, Господа, за ценные предложения (которые, к сожалению, Вы так и не высказали)! Разобрался сам. Вот код, если кому интересно:

public class Main {
    private static int [] fn = new int[100];

    static int fib(int x) {
        if (fn[x] == 0) {
            if (x == 1 || x == 2) {
                fn[x] = 1;
            } else {                
                fn[x] = fib(x - 2) + fib(x - 1);
            }
            System.out.println(fn[x]);
        }
        
        return fn[x];
    }

    public static void main(String[] args) {
	fib(5);
    }
}

Рекурсия с запоминанием тут получается благодаря массиву fn.