[자료구조] - 2. 재귀

재귀

 

• 재귀적(recursive) 알고리즘 : 알고리즘 자신을 사용하여 정의된 알고리즘

 

• 재귀의 요소
  • 재귀 케이스(recursion)
    : 차후의 재귀호출은 작아진 부문제들(subproblems)을 대상으로 이루어진다
  • 베이스 케이스(base case)
    : 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다.

 

 

 재귀 알고리즘에 대해서 살펴보겠습니다. '재귀(再歸)'라는 단어는 일상에 잘 쓰이지 않는 단어라 쉽게 이해되지 않는 것이 사실입니다. 재귀를 한자를 그대로 풀어보면 다시(再) 돌아오다(歸)라는 뜻입니다. 재귀를 부르는 원래 단어 recursion 역시 '반복, 되풀이' 라는 뜻입니다. 따라서, 재귀 알고리즘은 (자기 자신으로) 다시 돌아오는 알고리즘 이라고 할수 있겠습니다. 

 

int fac(int n) {				// n! 구하는 함수
	if (n == 1)				// Base case
		return 1;
	else					// recursion
		return n * fac(n - 1);
}

 

 백문이 불여일견, 빠른 이해를 위해 재귀를 이용한 함수 예시를 보여드리겠습니다. 위에 보여드린 fac() 함수는 정수 n이 주어졌을때, n!=n*(n-1)*(n-2)...*1 을 반환하는 함수를 C언어로 구현한 예시 입니다.

 여기에서 베이스 케이스는  n=1일때 1을 반환하는 부분으로, n=1이면 충분히 작아져서 더이상 재귀가 필요없으므로 그대로 1을 반환합니다.

 재귀 케이스는 n이 1이 아닌 경우, n*fac(n-1)을 반환하는 부분입니다. 여기서는 n이 충분히 작아진 값(1)이 될때 까지 자기 자신( fac 함수 )을 호출하게 됩니다.

 

재귀를 이용하여 팩토리얼을 구하는 함수 실행 예

 

 이해를 돕기 위해 함수 중간에 진행과정을 볼 수 있도록 출력함수를 추가했습니다. 진행과정을 보면, 처음 입력받은 정수 n=5에서 4, 3, 2, 1까지 감소하면서 다시 돌아오게 되고, 마침내 n=1이 되면 1을 반환합니다. 1을 반환받는 것은 n=2일때 이므로, 이때는 2*1를 반환합니다. 그 다음으로 n=3일때 3*(2*1)를 반환, n=4일때 4*(3*2*1)을 반환, 마지막으로 n=5일때 5*(4*3*2*1)을 반환하면서 함수가 끝나게 됩니다.

 진행 과정을 다른 방법으로 설명하자면,

fac(5) = 5 * fac(4) fac(5) = 5 * 4 * fac(3) fac(5) = 5 * 4 * 3 * fac(2) fac(5) = 5 * 4 * 3 * 2 * fac(1) fac(5) = 5 * 4 * 3 * 2 * 1  fac(5) = 120

​이와 같은 방법으로 진행되게 됩니다.

 

---

• 재귀 사용시 기본 규칙
  • 1. 베이스 케이스를 항상 가져야 한다.
  • 2. 재귀호출은 항상 베이스 케이스를 향하는 방향으로 진행해야 한다.
  • 3. 꼭 필요할 때만 사용한다.    ( 재귀 사용시 저장/복구 때문에 성능 저하 )

 

• 잘못 설계된 재귀
  • 예시 : 베이스 케이스가 없거나, 베이스 케이스에 도달할 수 없음
  • 결과 : 부정확한 결과, 재귀함수가 정지하지 않음, 저장을 위한 기억장소가 고갈됨

 

 재귀함수를 사용할 때의 주의사항은 다음과 같습니다. 재귀함수는 베이스 케이스를 가져야 하며, 재귀 호출은 반드시 베이스 케이스를 향하는 방향으로 진행해야 합니다.

 

1번. 재귀 호출이 베이스케이스를 향하지 않는 예

2번. 베이스 케이스가 없는 재귀함수의 예

 

 잘못된 재귀의 예를 작성해서 실행해 보았습니다. 앞서 사용한 fac함수를 조금 수정해서 사용해 보았습니다. 먼저 1번, 베이스 케이스 n=1로 향하지 않는경우, n이 무한히 커지다가 결국 오류가 나게 됩니다. 2번, 베이스 케이스 n=1이 없는 경우에는 n이 n=1에서 멈추지 않고 계속해서 감소하다가 오류가 나게 됩니다.