2. 순환

2.1 순환 소개

순환 : 어떤 알고리즘이나 함수가 자기 자신을 호풀하여 문제를 해결하는 기법

 

순환 알고리즘 구조

순환을 멈추는 부분 + 순환 호출을 하는 부분

 

만약, 호출을 멈추는 부분이 없다면

int factorial(int n) {

printf("factorial (%d)\n",n);

//if(n<=1) return 1;

//else

return n*factorial(n-1);

}

 

위의 코드를 작동시킨다면 프로그램을 무한호출을 하고 결국 오류를 발생시킴

 

순환과 반복

반복

• for, while 등으로 반복구조를 되풀이하는 방법
• 반복 제어 변수를 사용해 일정횟수나 조건이 만족될때까지 반복시킬 수 있음
• 간단하고 효율적인 구현방법

때때로 반복문을 사용하면 복잡해지는 문제가 있음 --> 순환이 적절함

ex) 순환적인 문제들

 

보통 반복과 순환은 문제해결능력이 동등, 어떤 한 문제에 두 알고리즘을 모두 사용 가능

ex) 순환 -> 반복, 반복 -> 순환

순환은 반복에 비해 알고리즘을 명확하게 간결하게 표현 가능

순환은 매구간 함수 호출 --> 보통 반복에 비해 수행속도가 느릴 수 있음

 

순환 원리

순환은 분할정복(Divide & Conquer)을 구현

--> 문제의 일부분을 해결한 뒤, 문제의 나머지 부분에 대해 순환호출

 

순환 알고리즘 성능

반복 알고리즘의 시간복잡도 : O(n)

순환 알고리즘의 시간복잡도 : O(n)

 

반복과 순환의 시간복잡도는 같지만, 순환은 함수 호출을 위한 매개변수 스택저장, 여분의 기억공간 등 사전작업 필요

---

2.2 거듭제곱 계산

팩토리얼 계산은 반복이 빠름

거듭제곱 계산은 순환이 빠름

 

거듭제곱 계산에서 순환이 빠른 이유는 문제의 크기가 절반씩 감소하기 때문

거듭제곱 반복문의 시간복잡도 : O(n)

거듭제곱 순환문의 시간복잡도 : O(log n)