🤖 2. 순환

순환이란?
어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
=> 함수 호출의 오버헤드 (실제 프로그래밍 걸리는 시간X, 낭비시간!!)

✅ 구조
① 순환을 멈추는 부분
    🚨 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출하다가 오류를 내면서 멈춤

② 순환 호출을 하는 부분

반복이란?
for나 while 등의 반복구조로 되풀이 하는 방법
=> 순환적인 문제에 대해서는 어려울 수 있음
=> 수행 속도가 빠름

✏️ 팩토리얼

• 순환

int factorial (int n) {  // O(n)
	if(n <= 1) return 1;    // 순환을 멈추는 부분
    else return (n * factorial (n-1));    // 순환을 호출하는 부분
}

f(n) = 1 + f(n-1) = f(1) + f(n-1) => O(n)
f(n-1) = 1 + f(n-2)
f(n-2) = 1 + f(n-3)
...
f(2) = 1 + f(1) = 1 + 1 = 2

• 반복

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

✏️ 거듭제곱값 계산

• 반복

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

• 순환

n이 짝수	n이 홀수
power(x, n) = power(x², n/2) = (x²)^n/2 = x^2(n/2) = x^n	power(x, n) = x·power(x², (n-1)/2) = x·(x²)^(n-1)/2 = x·x^(n-1) = x^n

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

한 번의 순환 호출을 할 때마다 문제의 크기는 약 절반으로 줄어듦 2^k -> 2^(k-1) -> 2^(k-2) -> ... -> 2^1 -> 2^0 => n=2^k => logn=k => O(logn)

✏️ 피보나치 수열의 계산

• 순환

int fib(int n) {  // O(2^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^1.7n)

ex) fib(6) -> fib( )함수 25번 호출 => 비효율적

• 반복

int fib_iter(int n) {  // O(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;
}

✏️ 하노이탑 문제

✅ 문제
막대 A에 쌓여있는 원판 3개를 막대 C로 옮기는 것

✅ 조건
· 한 번에 하나의 원판만 이동 가능
· 맨 위에 있는 원판만 이동 가능
· 크기가 작은 원판 위에 큰 원판 쌓일 수 없음

원판	1개	2개	3개	...	n개
이동	1번	3번	7번	...	(2^n -1)번

#include <stdio.h>

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

int main(void) {
	hanoi_tower(4, 'A', 'B', 'C');
    return 0;
}

📍 반복적인 형태로 바꾸기 어려운 순환

• 꼬리 순환(tail recursion) : 순환 호출이 순환 함수의 맨 끝에서 이루어지는 형태의 순환 => 반복으로 변환 가능
  ex) return n*factorial(n-1);
  
• 머리 순환(head recursion) : 여러 군데에서 자기 자신을 호출하는 경우(multi recursion) => 반복으로 쉽게 변환 불가능
  ex) return factorial(n-1)*2
  ex) 하이노탑