02. 순환

- 학습목표

• 순환의 개념을 이해한다
• 순환 알고리즘의 구조를 이해한다
• 순환 호출 시 주의사항을 이해한다
• 순환 호출 응용력을 배양한다

2.1 순환의 소개

순환?

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

순환 알고리즘의 구조

   - 순환 호출 하는 부분

   - 순환 호출을 멈추는 부분

을 포함한다.

만일, 순환 호출을 멈추는 부분이 없다면, 무한정 호출하게 되어 서버가 다운될 수 있으므로 주의하여야한다.

순환과 반복

• 순환 recursion: 순환 호출을 이용
  - 순환적인 문제에서 유리하다. 
  - 함수 호출의 오버헤드가 있다. -> 순환 호출 시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야하기 때문에 여분의 기억장소가 필요하다. -> 비효율적인 경우가 많음

 

• 반복 iteration: for or while 을 이용한 반복
  - 일반적으로 수행속도가 빠르다.
  - 순환적인 문제를 반복으로 바꾸려면, 프로그램 작성이 다소 어려울 수 있다.

그러나, "순환문이 무조건 더 유리하고, 반복문이 무조건 수행속도가 빠르다" 는 아니다!

순환의 예

1. 팩토리얼 값 구하기

n! = 1 (n = 0)
    = n * (n - 1) (n >= 1)

• 순환을 이용

int factorial(int n) {
	if (n <= 1) return 1;
    else return (n * factorial(n - 1));
}

• 반복을 이용

int factorial(int n) {
	int result = 1;
	for (int i = 1; i <= n; i++) { 
    	result = result * i;
    }
    return result;
}

=> 순환이 더 직관적이고, 이해하기 쉬움

 

 

2. 피보나치 수열

      * 피보나치 수열? 앞의 두개의 숫자를 더해 뒤의 숫자를 만든다 e.g) 0, 1, 1, 2, 3, 5, 8 .....

• 순환을 이용

int fib(int n) {
	if (n == 0) return 0;
    if (n == 1) return 1;
    return (fib(n - 1) + fib(n - 2));
}

T(n) = T(n-1) + T(n-2) + C 를 빅오표기법으로 나타내면, 

O(2^n)이다.

• 반복을 이용

int fib(int n) {
	if(n == 0) return 0;
    if(n == 1) return 1;
    
    int first = 0;
    int second = 1; 
    int result = 0; 
    
    for (int i =2; i <= n; i++) {
    	result = first + second;
        first = second;
        second = result;
     }
        
    return result;   
}

for문이 한번 존재 하므로, 빅오표기법은 O(n)이다.

=> 순환문이 더 간결하지만, 반복문이 더 효율적이다. 

왜일까?

피보나치 순환문의 비효율성

등 의 예외가 존재하기 떄문에, 상황에 따라 알맞게 선택하여야 한다.