2. 순환

1. 순환

순환: 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

ex) 팩토리얼, 거듭제곱, 피보나치수열, 이항 계수, 이진트리 알고리즘, 이진 탐색, 하노이 탑 등

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

- 순환적인 방법이 반복적인 방법에 비해 빠른 경우: 거듭제곱 계산 O(log₂n) > O(n) 

- 순환적인 방법이 반복적인 방법보다 느린 경우: 피보나치수열  O(2ⁿ) < O(n) 

 

2-2. 거듭제곱 계산

- x^n = (x^2)^n/2

- n = 2m+1 -> m = (n-1)/2

- x^2m+1 -> x*x^2m -> x*(x^2)^m

따라서 짝수일 경우 power(x*x, n/2), 홀수일 경우 x*power(x*x,(n-1)/2) 호출, 이때 시간 복잡도는 O(log₂n)

 

2-3. 하노이탑 

- 한번 순환 호출 시 두 개의 함수와 한 번의 연산으로 나누어짐.