자료 구조 - 재귀

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

재귀

재귀(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다.

순환 호출의 내부적인 구현

함수를 순환 호출했을 때의 과정을 살펴 본다.

1. 다른 함수를 호출하는 것과 비슷하게 자기 자신을 호출한다.
   • 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 파라미터와 지역 변수를 스택으로부터 할당받는다.
     • 이런 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라고 한다.
     • 순환 호출이 중첩될수록 시스템 스택에 활성 레코드들이 쌓인다.
2. 준비가 끝나면 호출된 함수의 코드 시작 위치로 이동해 수행을 시작한다.
3. 호출된 함수가 끝나면 시스템 스택에서 복귀주소를 꺼내 자신을 호출한 함수로 돌아간다.

순환 vs 반복

• 일반적으로 순환과 반복 알고리즘은 서로 바꾸어 구현 가능하다.
• 보통 순환 이 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
• 그렇지만 순환은 함수 호출을 하므로 반복에 비해 수행속도 면에서 떨어진다.
• 공간 복잡도도 높다.

순환의 원리

• 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할 정복(divide and conquer)이라고 하는데, 순환은 이 방법을 사용한다.

반복적인 형태로 바꾸기 어려운 순환

return n * factorial(n-1);
return factorial(n-1) * n;

• 첫 문장을 꼬리 순환 이라고 하고, 두 번째 문장을 머리 순환이라고 한다.
• 하노이 탑 같은 다중 순환이나, 머리 순환은 반복적인 형태로 바꾸기 어렵다.

다중 순환

• 선형 순환 (linear recursion)
  • 하나의 호출 발생시 최대 하나의 순환 호출
• 다중 순환 (multiple recursion)
  • 하나의 함수에서 두 개 이상의 순환 호출
  • 하노이 탑 같은 경우.