재귀함수

• 자기 자신을 호출하는 함수
• 스택 프레임
• 복귀 라인을 기억해놓음
• if - else 형식으로 탈출조건 작성하기

피보나치

import java.util.*;
public class Main {

    static int[] fibo;

    //num이 항의 번호
    public static int recursive(int num){
        if (num==1) return fibo[num]=1;
        else if (num==2) return fibo[num]=1;
        else {
            return fibo[num] = recursive(num-2)+recursive(num-1);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int input = in.nextInt();
        //성능을 올리기 위해 배열 사용
        fibo = new int[input+1];
        recursive(input);
        for (int i=1;i<=input; i++){
            System.out.print(fibo[i]+" ");
        }


    }


}

• 이렇게 배열을 사용해서 성능을 최적화 할 수 있음

import java.util.*;
public class Main {

    static int[] fibo;

    //num이 항의 번호
    public static int recursive(int num){
        if (fibo[num]!=0) return fibo[num];
        if (num==1) return fibo[num]=1;
        else if (num==2) return fibo[num]=1;
        else {
            return fibo[num] = recursive(num-2)+recursive(num-1);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int input = in.nextInt();
        //성능을 올리기 위해 배열 사용
        fibo = new int[input+1];
        recursive(input);
        for (int i=1;i<=input; i++){
            System.out.print(fibo[i]+" ");
        }


    }


}

• 더해서 메모이제이션을 사용하면 훨씬 빨라짐
• 값을 기록해놓고 기록한 것을 사용
• 재귀 호출이 훨씬 적어짐