재귀 (Recursion)

1. 개념

출처 : https://www.programiz.com/cpp-programming/recursion

재귀 함수는 간단히 말해 자기 자신을 호출하는 함수이다. 위 그림처럼 recurse 함수가 내부에서 다시 recurse 함수를 호출하는 것이 재귀 함수의 예시이다. 종료 조건이 없다면 무한으로 호출되기 때문에 함수를 정의할 때 종료 조건부터 설정해야 한다.

2. 장단점

- 장점

문제를 해결하는 데 있어서 재귀를 사용했을 시, 가독성과 간결성의 향상을 기대할 수 있다.

- 단점

함수 호출에 대한 오버헤드가 존재하며 재귀가 진행함에 따라 호출 스택이 쌓이기 때문에 스택 오버플로우가 발생할 위험이 있다.

3. 예시

- 팩토리얼 (n!)

int Factorial(int n)
{
	if (n <= 1) return 1; // 종료 조건

	return n * Factorial(n - 1);
}

- 피보나치 수열

int Fibonacci(int n)
{
	if (n <= 1) return 1; // 종료 조건
	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

- 재귀 이진 탐색

// 구현부
int RecurseBinarySearch(int* arr, int left, int right, int target)
{
	if (left <= right)
	{
		int middle = (left + right) / 2;

		if (arr[middle] > target)
		{
			return RecurseBinarySearch(arr, left, middle - 1, target);
		}
		else if (arr[middle] < target)
		{
			return RecurseBinarySearch(arr, middle + 1, right, target);
		}
		else
		{
			return middle; // 찾으면 해당 index 반환
		}
	}
	
	return -1; // 찾을 수 없다면 -1 반환
}

// 실행부
int main()
{
	int arr[]{ 2, 4, 6, 8, 10 }; // 정렬된 배열이라고 가정
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << RecurseBinarySearch(arr, 0, size - 1, 8) << " ";
	cout << RecurseBinarySearch(arr, 0, size - 1, 9) << endl;
    // 출력 : 3 -1
}