[JAVA] 재귀함수 ( 메모이제이션 )

재귀 알고리즘 

재귀(Revursion) 함수란 특정 함수 내에서 자신을 다시 호출하여 문제를 해결해나가는 함수이다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 해결함으로써 원래 문제를 해결해 나가는 방식이다. 일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며 반대로 재귀함수로 구현 가능한 기능을 반복문으로 구현이 가능하다.

 

재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간이 되는 BaseCase를 생각하여 코드를 구현해야 한다. 아래는 샘플예제이다.

public class Recursion
{
    public static void main(String[] args)
    {
        Function();
    }
    
    public static void Function()
    {
        System.out.println("반갑습니다");
 
        Function();
    }
}

 

Funtion 함수의 기능은 "반갑습니다"를 호출하고 다시 자기 자신을 호출하고 있다. 해당 소스에서 문제는 자기 자신을 호출만하고 있지 함수 영역이 종료되는 구간이 없기 때문에 무한반복되는 루프에 빠지게 된다.

 

public class Recursion_Test
{
    public static void main(String[] args)
    {
        Function(5);
    }
 
    public static void Function()
    {
        if(num==0)
        {
        return;
        }
        else
        {
        	System.out.println("반갑습니다.");
            Function(num-1);
    }
}

 

이렇게 수정한 결과, 매개변수 값이 0일 경우 return을 하고 아닐경우 "반갑습니다"를 출력하고 num-1에 해당하는 값을 매개변수로 전달하고 있다. 여기서 num 이 0일 경우 return을 하게 되는 구문이 재귀 함수의  BaseCase구간이 된다.

해당 재쉬 함수의 호출을 그림으로 보면 아래와 같다.

 

 

 

 

 

예제 : 1부터 n까지 합 구하기 ( recursive )

위에서 배운 재귀 알고리즘을 적용하여 1부터 n까지 합을 구하는 재귀함수를 구현해본다.

 

public class Recursion
{
    public static void main(String[] args)
    {
        System.out.println("1부터 5까지의 합은 : " + Function(5));
    }
 
    public static int Function(int num)
    {
        if(num == 1)
        {
            return 1;
        }
        else
        {
            return num + Function(num -1);
        }
    }
}

 

 

 

예제 : 입력받은 정수 n을 2진수로 출력하기 ( recursive )

class Recursive {
    public void recursive(int n) {
       if(n==0)
           return;
       else{
           recursive(n/2);
           System.out.print(n%2);
       }
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        T.recursive(11);
    }
}
//////////
입력 : 11 
출력 : 1011

 

 

 

예제 : 팩토리얼 ( recursive )

입력받은 정수 n의 팩토리얼 값을 출력하시오.

public class Recursive {
	// 반환받아야하니 int
    public int recursive(int n) {
       if(n==1) return 1;
       else return n*recursive(n-1);
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        System.out.println(T.recursive(5));
    }
}
//////////
입력 : 5
출력 : 5*4*3*2*1 = 120

 

 

 

 

 

예제 : 피보나치 ( recursive )

1. 가장 기본적인 피보나치 recursive 

public class Solution {
    public int recursive(int n) {
       if(n==1) return 1;
       else if(n==2) return 1;
       else return recursive(n-1)+recursive(n-2);
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        int n=10;
        for(int i=1; i<=n; i++) System.out.print(T.recursive(i)+" ");
    }
}

 

 

2. 조금 더 최적화된 피보나치 recursive

public class Solution {
    static int[] fibo;
    public int recursive(int n) {
       if(n==1) return fibo[n]=1;
       else if(n==2) return fibo[n]=1;
       else return fibo[n]=recursive(n-1)+recursive(n-2);
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        int n=10;
        fibo=new int[n+1];
        T.recursive(n);
        for(int i=1; i<=n; i++) System.out.print(T.recursive(i)+" ");
    }
}

 

 

메모이제이션을 활용한 피보나치 recursive ( 가장 최적화 )

메모이제이션(memoization)이란 ?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술. 동적 계획법의 핵심이 되는 기술이다.

 

메모이제이션을 사용하여 배열을 하나 만들고 값을 재사용하여 풀이한 결과, 재귀만을 사용한 위의 풀이 방법과 비교하여 실행속도에 엄청난 차이가 있다.

 

 

public class Solution {
    static int[] fibo;
    public int recursive(int n) {
       if(fibo[n]>0) return fibo[n];
       if(n==1) return fibo[n]=1;
       else if(n==2) return fibo[n]=1;
       else return fibo[n]=recursive(n-2)+recursive(n-1);
    }
    public static void main(String[] args) {
        Solution T=new Solution();
        int n=45;
        fibo=new int[n+1];
        T.recursive(n);
        for(int i=1; i<=n; i++) System.out.print(T.recursive(i)+" ");
    }
}