2.1 순환의 소개

순환

순환(Recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

순환의 예

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

반복

반복(Iteration)이란 for나 while 등의 반복 구조로 되풀이하는 방법이다.

반복의 예

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

2.2 거듭제곱값 계산

반복적인 거듭제곱 계산

double power_iter(double x, int n) {
	double result = 1.0;
    for (i = 0; i < n; i++) {
    	result = result * x;
    }
    return result;
}

• 시간 복잡도: O(n)

순환적인 거듭제곱 계산

double power(double x, int n) {
	if (n == 0) return 1;
    if (n % 2 == 0) return power(x * x, n / 2);
    return x * power(x * x, (n - 1) / 2);
}

• 시간 복잡도: O(logn

2.3 피보나치 수열의 계산

반복적인 피보나치 수열 계산

int fib_iter(int n) {
	if (n == 0) return 0;
    if (n == 1) return 1;
    
    int pp = 0;
    int p = 1;
    int result = 0;
    for (int i = 2; i <= n; i++) {
    	result = p + pp;
        pp = p;
        p = result;
    }
    return result;
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

순환적인 피보나치 수열 계산

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

• 시간 복잡도: O(2^n)
• 공간 복잡도: O(n)

2.4 하노이탑 문제

void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) System.out.printf("원판 1을 %c에서 %c로 옯긴다.\n", from, to);
    else {
    	hanoi_tower(n - 1, from, to, tmp);
        printf("원판 %d을 %c에서 %c로 옮긴다.\n", n, from, to);
        hanoi_toewr(n - 1, tmp, from, to);
    }
}

• 시간 복잡도: O(2^n)
• 공간 복잡도: O(n)