[자료구조] 순환 정의, 종류, 순환함수, 반복과 비교

✅ 순환(recursion)

• 정의
  • 정의 하려는 개념 자체를 정의 속에 포함하여 이용
  • 함수의 똑같은 이름을 계속 불러줌으로써 같은 일을 반복하는 것
• 종류
  • 직접순환 : 함수가 직접 자신을 호출
  • 간접순환 : 다른 제 3의 함수 호출 → 3의 함수가 다시 자신 호출
• 적용
  • 분할정복(divide and conquer)의 특성을 가진 문제에 적합
  • 복잡한 문제를 작은 문제로 분할하여 해결하는 방법
  • 분할한 문제와 원래의 문제가 성질이 동일하여 푸는 방법도 동일
  • 종료 조건이 만족할 때 까지 같은 동작을 순환
• 명령문 골격
  • if ( 조건문 ) → 종료조건 : 간단한 케이스로 끝나는 경우
  • else → 순환 호출 : 간단한 케이스로 분할한 것을 다시 call

✅ 순환함수의 예

• 1️⃣ 순환함수 예시(1) - factorial

int factorial(int n) {
	if (n <=1) return (1); //종료조건
	else return ( n*factorial(n-1) ); //순환함수
}

factorial(5)

= 5 * factorial(4)

= 5 4 factorial(3)

= 5 4 3 * factorial(2)

= 5 4 3 2 factorial(1)

= 5 4 3 2 1

= 120

• 2️⃣ 순환함수 예(2) - binsearch : 주어진 key 값이 저장된 배열 a[ ]의 위치 (인덱스, mid)를 찾아내는 방법
  

binsearch (a[], key, left, right) {
	if (left > right) {
		return -1; //종료조건
	} else {
			mid = (right+left)/2;
			if (key = a[mid]) return mid;
			else if (key < a[mid]) return (binsearch(a, key, left, mid-1)); //순환호출
			else if (key > a[mid]) return (binsearch(a, key, mid+1, right)); //순환호출
	}
}

💡 배열의 수가 정렬되어있는 경우만 가능

✅ 순환 vs 반복

• 순환
  • 순환 함수를 반복호출하는 법
  • 큰 문제를 작은 문제로 나눠서 해결하려는 방법
  • 순환적인 문제에서는 자연스러운 방법
  • 함수 호출의 오버헤드가 크다
• 반복
  • for나 while을 이용한 반복하는 법
  • 프로그램의 수행속도가 상대적으로 빠르다
  • 순환적인 문제에 대해서는 프로그램 작성이 어려울 수 있다