3장-6. 재귀 함수

선형 재귀

• 재귀의 가장 간단한 형태
• 호출이 발생할 때 최대 하나의 재귀호출이 발생함

#include <iostream>

int LinearSum(int* arr, int n)
{
	if (n == 1)
		return arr[0];

	else
		return LinearSum(arr, n - 1) + arr[n - 1];
}

int main()
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	int sum = LinearSum(arr, 10);
	std::cout << sum << std::endl;

	return 0;
}

 

선형 재귀 알고리즘의 형태

• 기저 사례는 재귀 호출의 모든 연결이 결국 하나의 기저 사례로 정의되어야 함
• 각 기저 사례에서는 재귀를 사용해선 안된다!

 

선형 재귀법을 이용한 원소 반전

void ReverseArray(int* arr, int start, int end)
{
	if (start < end)
	{
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;

		ReverseArray(arr, start + 1, end - 1);
	}

	return;
}

• 이 알고리즘은 start == end, start > end 총 두 개의 기저 사례를 가지고 있다.
• arr가 홀수라면 start == end일 것이고, 짝수라면 start > end의 상황에 도달하게 되기 때문

 

 

 

 

 

---

후미 재귀

• 재귀 함수를 사용할 때는 성능도 생각해야 한다.
• 컴퓨터 메모리가 부족할 때는 재귀 알고리즘에서 비재귀 알고리즘을 이끌어내야 함

void iterativeReverseArray(int* arr, int start, int end)
{
	while (start < end)
	{
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;

		start = start + 1;
		end = end - 1;
	}
}

• 앞선 예제 원소 반전 문제를 비재귀 알고리즘으로 이끌어냄

 

 

 

 

 

---

이진 재귀

• 알고리즘이 2개의 재귀 호출을 만드는 경우를 이진 재귀라고 한다.
• 어떤 문제를 똑같이 반으로 나누어 푸는데 사용할 수 있다.

 

1. arr의 전반 원소들에 대해 재귀적으로 합을 구함
2. arr의 후반 원소들에 대해 재귀적으로 합을 구함
3. 두 결과를 더한다.

 

int BinarySum(int* arr, int start, int count)
{
	if (count == 1)
		return arr[start];

	else
		return BinarySum(arr, start, count / 2) + BinarySum(arr, start + (count / 2), count / 2);
}