Recursion(재귀)

함수가 자기 자신을 적어도 한번 이상 호출한다면, 그것은 재귀함수이다. 재귀 함수를 시각화 했을때, 재귀 트리의 가지가 뻗어나가는 모양에 따라, 재귀 알고리즘을 분류할 수 있다.

• Linear Recursion : 가지가 갈라지지 않는 경우
• Binary Recursion : English Ruler 문제 같은 경우
• Multiple Recursion : abc, acb, bac...... 같은 조합 문제일 경우

재귀 함수의 장점은 정의가 간단하다는 것이고, nested for loop 같은 가독성이 좋지 않은 코드를 피할 수 있다는 점에 있다. 

그러나, 함수를 호출하면, 컴퓨터는 이를 메모리에 기록하고, 함수가 반환될 때까지, 호출 스택에 쌓이게 된다.

따라서 메모리가 한정적인 상황이라면, 재귀 알고리즘을 비재귀 알고리즘으로 바꾸는 것이 유리하다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 재귀 함수 버전
void reverseArray_0(int* arr, size_t start, size_t end){
	if(start < end){
		std::swap(arr[start], arr[end]);
		reverseArray_0(arr, start + 1, end - 1);
	}
}

// 비재귀 함수 버전
void reverseArray_1(std::vector<int>& arr){
	size_t start = 0;
	size_t end = arr.size() - 1;
	do{
		std::swap(arr[start], arr[end]);
		start = start + 1;
		end = end - 1;

	} while(start < end);
}

// 원소 출력
void printArray(std::vector<int>& arr){
	for(auto& ele : arr){
		cout << ele << " ";
	}
	cout << endl;
}

auto main() -> int{
	vector<int> arr { 1,2,3,4,5,6,7,8,9,0 };

	reverseArray_0(arr.data(), 0, 9);

	printArray(arr);

	reverseArray_1(arr);

	printArray(arr);

}

 

참고

https://visualgo.net/en/recursion