쓰이는 알고리즘 - Recursive Call (재귀 호출) 언제 쓸까?

쓰이는 알고리즘 - 재귀 호출

 

 

 

1. 재귀 호출이란?

 

- 함수 안에서 동일한 함수를 호출하는 형태

 

- 어떤 상황에서 하나의 큰 문제가 여러 개의 같은 작은 문제로 분할(분할 정복)하여 해결가능한 경우 사용됨

 

- function(n)의 결과 값에 function(n-1)이 포함된 경우

 

- 동일한 process를 쪼개고 쪼개다 보면 멈춰지는 지점이 있음 (러시아 인형이랄까.. 인형안에 인형. 인형안에 인형...)

 

---

 

2. 재귀 호출의 패턴

 

public int function(arg){
    if (arg > n){
    	return function(arg-1);
    } else{
    	return m;
    }
}

public int function(arg){
    if (arg <= n){
    	return m;
    }
    function(arg-1);
    return m;
}

public int function(arg){
    if (arg <= n){
    	return m;
    }
    
    if (condition){
    	function(arg~);
    }else if(other condition){
    	function(arg~');
    }
}

 

 

이 때, 호출되는 함수는 stack으로 관리된다. 예를 들어, function(5)를 arg=1일 때 까지 recursive call된다면, function(1)이 제일 먼저 수행되고, function(5)가 제일 마지막에 수행된다.

 

---

 

3. 분할 정복이란?

 

- 문제를 나눌 수 없을 때까지 나워서 각각을 해결하고, 합병해서 최종적으로 전체 문제를 해결하는 알고리즘

 

- 하향식 접근법(상위 문제를 해결하기 위해 아래로 내려가면서 하위 문제를 해결하는 방식)

 

- 일반적으로 재귀 호출 이용

 

---

 

4. 동적계획법

 

- 문제를 잘게 쪼개서 가장 작은 부분부터 해결한 후, 해당 결과값을 바탕으로 보다 큰 문제를 해결하고, 최종적으로 전체 문제를 해결하는 알고리즘

 

- 상향식 접근법(최하위 해답 -> 저장 -> 상위 문제 해결)

 

- Memoization 기법을 활용: 전에 계산한 값을 저장해서 다시 계산하는 과정을 생략해 전체 실행 속도를 빠르게 하는 기술

 

- 재귀 호출을 이용할 수 있으나, 많은 재귀 함수가 stack에 쌓여 성능 상 좋지 않을 수 있다.

 

- 피보나치 수열이 대표적인 예

 

 

두 알고리즘은 최종 문제 해결을 위해 문제를 나눈다는 측면에서 유사하다.

하지만, 동적 계획법은 부분 문제가 중복되어(작은 문제가 큰 문제에 포함됨) 상위 문제 해결 시 재활용되어 Memoization 기법을 사용하고.

분할 정복은 부분 문제가 중복되지 않아 하위 문제의 해결값이 재활용되지 않는다.

 

// 재귀 호출을 통한 피보나치 수열 해 찾기
public int fibo(int arg){
    if (arg <= 1)
    	return arg;
    return fibo(arg-1) + fibo(arg-2);
}

fibo(4)를 호출할 경우,
fibo(4) = fibo(3) + fibo(2)
		= fibo(2) + fibo(1) + fibo(1) + fibo(0)
        = fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0)
        
이와 같이 상대적으로 많은 function이 stack에 쌓여 성능문제를 초래할 수 있다.


// 동적 계획법을 통한 피보나치 수열 해 찾기
public int fibo(int arg){
    int[] cache = new int[arg+1];
    cache[0] = 0;
    cache[1] = 1;
    
    for(int i=2; i<arg+1; i++){
    	cache[i] = cache[i-1] + cache[i-2];
    }
    return cache[arg];
}

이전에 사용된 값을 그대로 재활용하고 있다.