[알고리즘 정리] 재귀

 

 

다룰 내용

• 재귀란 무엇인가?
• 재귀를 구현할 때 주의할 점
• Factorial
• Fibonachi

---

 

재귀란 무엇인가?

자신의 메소드 내부에서 자신의 메소드를 호출하는 것

 

 

재귀를 구현할 때 주의할 점

1) 메소드의 역할을 명확히 해야 함.

2) 자신이 해야할 일과 나머지 작업으로 분리해야 함.

 

3) 기저 조건이 반드시 있어야 함. (재귀 탈출 조건) -> 기저가 없으면 스택 오버 플로우 발생

4) 재귀의 깊이를 생각해야 함. (상태 공간 트리 활용)

5) 깊이뿐만 아니라 수행시간도 고려해야 함. 

 

 

Factorial

5! -> 5 * 4 * 3 * 2 * 1

    => 이는 5 * 4! 형태로 이해할 수 있음.

    => 또 5 * 4 * 3! 형태로도 이해할 수 있음.

    => 5 * 4 * 3 * 2! 형태

    => 5 * 4 * 3 * 2 * 1!

 

일반화하면

n!  = n * (n - 1)!

 

1!이 계산되어야 2!이 계산되고 이가 선행되어야 3!이 계산되는 형태

 

스택 구조를 보게 되면 1!이 제일 먼저 연산되고 호출됐던 메소드로 돌아가며 결과 값을 전달해주는 형태임.

1!

2!

3!

4!

5!

<Stack>

 

 

다음과 같이 코드로 구현할 수 있음.

public class FactorialTest {

	public static void main(String args[]){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        System.out.println(Factorial(n));
    }
    
    private static long Factorial(int n){
    	// 기저 조건
        if(n == 1) return 1;
        
        // 유도 파트(메소드가 수행해야 하는 일)
        return n * Factorial(n - 1);
    }
}

 

상태 공간 트리를 보게 되면

 

보는 것처럼 Factorial의 경우 재귀를 사용했을 때 리니어하게 호출이 되므로 재귀로 구현했을 때 효율적임.

 

 

Fibonachi

 

구하려는 항 n = (n - 1) 항 + (n - 2) 항

0	1	2	3	4	5
1	1	2	3	5	8

 

 

다음과 같이 코드로 구현할 수 있음.

public class FibonachiTest {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		System.out.println(fibonachi(n));
	}
	
	private static long fibonachi(int n) {
    	//기저 조건
		if(n <= 1) return n;
        
        // 유도 파트
		return fibonachi(n - 1) + fibonachi(n - 2);
	}
}   

 

상태 공간 트리를 그려 보면

 

위 그림과 같이 호출이 일어남. Factorial과 다르게 Fibonachi는 중복된 호출이 빈번하게 일어나기 때문에 수가 조금만 커져도 엄청난 수행 시간이 걸림. 

 

따라서 Fibonachi를 재귀로 구현할 경우 memoization을 하여 이미 연산된 값을 활용하는 것이 효율적임.

 

---

memoization이란? 기존 수행 결과를 저장해두었다가 필요 시에 저장된 값을 사용하는 것

이를 위해서는 추가적인 메모리 공간이 필요하고 이때 적절한 자료구조를 이용하여 활용할 수 있음.

 

 

Fibonachi에 memoization을 활용하면 아래와 같이 구현할 수 있음.

 

public class FibonachiMemoTest {

	static long memo[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		memo = new long[n + 1];
		
		System.out.println(fibonachi2(n));
	}
	
	/* 중복 호출이 많이 발생할 경우 메모하는 것이 유리하지만 그렇지 않으면 메모된 값이 있는지 없는지
	확인해봐야하기 때문에 중복 호출이 많지 않은 경우 그냥 재귀를 사용하는 것이 좋다. */
	private static long fibonachi2(int n) {
		if(n <= 1) return n;
		
		//n항의 값을 계산한 적이 있었다면 메모 확인하고 메모된 값 리턴
		if(memo[n] != 0) return memo[n];
		
        //메모의 값이 0일 때
		return memo[n] = fibonachi2(n - 1) + fibonachi2(n - 2);
	}
}