[📗c언어 쉽게 풀어쓴 자료구조2] 순환

👑 순환의 소개(팩토리얼 계산- 반복이 효율적)

• 순환: 어떤 알고리즘이나 함수가 자기자신을 호출하여 문제를 해결하는 기법 (반복으로 표현 가능! but 문제에 따라 순환이 효율적일 수도, 반복이 효울적일 수도)

• 분할정복방법 : 작은 문제로 분해하여 해결 (일부 해결 후 나머지 문제에 대해 순환 호출)

• 종료부 and 순환부
  -> 호출 시 스택에 활성 레코드가 기록이 되는데, 종료가 되지 않는다면 스택에 공간이 부족하여 오류 생성

• 팩토리얼 문제-순환

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

-> 꼬리순환: 'n*factorial(n - 1)'와 같이 순환 호출이 끝에서 이루어지는 경우 - 반복으로 표현 가능 (머리순환, 꼬리순환 모두 가능한 경우, 꼬리순환으로!!!)
-> 가독성, 간단, 쉬움 (but, 실행시간 오래걸림-함수 호출, 여분의 기억 장소 필요- 상태 기억해야하므로)

👑 거듭제곱값 계산- 순환이 효율적

double power(double x, int n) {
	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);
}

-> 시간 복잡도: O(log2n)

👑 피보나치 수열의 계산- 반복이 효율적

• 순환 호출 시 같은 것 여러 번 호출-> 매우 비효율적

👑 하노이탑 문제

: 순환의 대표적인 예제