#1 정의
어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.
#2 내부동작
순환을 이해하기 위해서는 함수의 호출 과정을 이해하고 있어야한다. 함수가 자기 자신을 호출하는 것은 다른 함수를 호출하는 것과 과정이 동일하다.
- 함수 호출
- 내부 동작 실행
- 실행 중 함수를 호출하게 됨
- 해당 함수를 실행
- 이하 생략…
#3 알고리즘의 구조
순환 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다.
def factorial(n:int):
if n <= 1: # 순환을 멈추는 부분
return 1
else: # 순환적으로 호출하는 부분
return n * factorial(n-1)#4 순환과 반복
반복이란 for, while과 같이 반복구조로 되풀이되는 방법이다. 순환은 순환적인 문제나 자료구조를 다루는 프로그램에 적합하다. 반복은 순환으로 순환은 반복으로 표현할 수 있다. 특히 순환이 꼬리 순환으로 표현되는 경우에 반복으로 쉽게 표현할 수 있다.
#5 순환의 원리
분할정복이란 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 기법이다. 순환알고리즘은 분할정복을 기반으로 한다. 순환 알고리즘은 자기 자신을 호출 할 때 문제가 동일한 형태로 크기는 작아진다. 문제의 일부를 해결한 다음 나머지 문제에 대해 순환 호출을 한다.
#6 순환의 성능
순환 알고리즘으로 작성 된 프로그램은 이해하기도 쉽고 가독성이 있다. 하지만 함수 호출 시 스택에 쌓는 오버헤드도 생기기 때문에 동일한 논리의 반복문과 비교할 때 시간과 공간을 더 소모한다.
#7 순환을 활용하는 문제
- 피보나치 수열의 계산
- 펙토리알 수의 계산
- 하노이 탑 문제