[자료구조] 순환

순환

• 순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
• ex) 팩토리얼, 피보나치, 이항계수 계산, 이진 탐색, DFS...

 

내부적인 구현

• 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드라 한다.

 

순환 알고리즘의 구조

• 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다.

 

순환의 원리

• 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법으로 분할정복(divide and conquer)이라 한다.
• 순환호출이 일어날 때마다 문제의 크기가 작아진다.
• 문제의 크기가 점점 작아지면 풀기가 쉬워지고 결국은 풀기 쉬운 문제가 된다.