[Algorithm] 재귀

• 재귀란
  • 하나의 메소드 내에서 자기 자신을 호출하도록 하여 반복하는 개념
  • 하나의 재귀 호출은 하나의 부분 문제를 해결한다. → 부분 문제를 푸는 재귀에서 또 다른 부분 문제를 푸는 재귀 호출 → 반복반복.. → 재귀는 점점 작아져 이어지는 부분 문제 없이 답이 나오고 종료된다.

 

• 재귀 정의 순서
  1. 상태 정의
     • 부분 문제는 하나의 문제에서 하나의 답이 나와야 한다.
     • 답을 결정하는 변수들을 상태라고 한다.
     • 한 부분 문제는 하나의 상태에 대한 답을 찾는 문제가 된다.
     • 예로 (x, y)로 상태 표기
  2. 종료 조건
     • 재귀가 진행될수록 상태는 작아지고, 마지막엔 이어지는 부분 없이 답이 나와야 한다. (재귀 종료)
     • 답을 반환할 수 있도록 하는 것을 종료 조건이라고 한다.
  3. 점화식
     • 가장 큰 상태가 어떤 과정을 거쳐 종료 조건에 도달하는지 정의
     • 부분 문제는 더 작은 부분 문제로 진행, 상태도 더 작은 상태로 전이, 이렇게 상태를 전이시키는 규칙을 점화식이라고 한다.

 

• 코드로 변환하기
  • 위에서 정의한 상태, 종료 조건, 점화식을 이용하여 코드 구현
  1. 입력 매개변수
     • 상태 변수는 메소드의 입력부에 들어간다.
       • 예로 private int recursion(int n, int m) { … }
  2. 종료 조건 작성
     • 조건 만족시 바로 답이 나오는 종료 조건을 먼저 작성한다.
       • 예로 if(n == 0) return 1; 같이 재귀 안돌아도 바로 답나오는 조건은 앞 부분에 코드 작성
  3. 점화식 작성
     1. return 부분에 점화식 작성
        1. 예로 recursion()라는 재귀 메소드라면 return n * recursion(n, m-1);
• 예시 코드

public class Ex {
	private int recursion(int n, int m) {
		if (n == 0) return 1;
		if (m == 0) return 1;
		if (n == 1) return 1;
		
		return n * recursion(n, m-1);
		}
}