[자료구조] L07. Recursion

• toc {:toc}

What is Recursion?

• 재귀(Recursion) : 함수 안에서 자기 함수를 다시 호출하는 방식을 한다.

  • 직접적 : 자기 자신을 직접 부르는 재귀적 구조
  • 간접적 : 두 함수 이상이 연결되어 서로를 호출하는 재귀적인 구조

• 함수는 호출 시 메모리의 스택 부분에 위치한다.

• 재귀를 사용할 경우 함수가 반복되어 사용되기 때문에 Stack overflow를 주의해야 한다.

• 재귀는 반복보다 효율적이지 않은 경우가 많지만, 간단하고 코드가 직관적이기 때문에 사용한다.

Structure of Recursion

• Base case : 비재귀적인 상태가 될 수 있도록 하는 경우이다. 재귀의 종료, 반환 조건이 된다.
• General (recursive) case : 자기 자신의 더 작은 버전으로 호출할 수 있는 조건이다.
• 재귀 알고리즘은 반복적으로 함수를 호출할수록 문제가 더 작아지는 구조로 표현되어야 한다.

int Factorial(int number){
	if (number == 0)
		return 1;
	else
		return number * Factorial(number-1);
}
// 시간 복잡도 : O(N)

• 파스칼의 공식을 사용해서 조합도 재귀적으로 표현할 수 있다.

int Combinations(int n, int k){
	if (k==1)
		return n;
	else if (n==k)
		return 1;
	else
		return Combination(n-1, k) + Combination(n-1, k-1);
}

template<class ItemType>
bool BinarySearch(ItemType)(ItemType info[], ItemType item,
							int fromLoc, int toLoc){
	int mid;
	if (fromLoc > toLoc)
		return false;
	else{
		mid = (fromLoc + toLoc) / 2;
		if (info[mid] == item)
			return true;
		else if (item < info[mid])
			return BinarySearch(info, item, fromLoc, mid-1);
		else
			return BinarySearch(info, item, mid+1, toLoc);
	}
}

• Sorted List의 재귀적 InsertItem

template <class ItemType>
void Insert(NodeType<ItemType>* &location, ItemType item){
	if ((location==NULL) || (item < location->info)){
		NodeType<ItemType>* tempPtr = location;
		location = new NodeType<ItemType>;
		location->info = item;
		location->next = tempPtr;
	}
	else
		Insert(location->next, newItem);
}
 
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType newItem){
	Insert(listData, newItem);
}

• InsertItem을 하면 이전 포인터의 다음 값이 insert item, insert item의 다음 값을 현재 값으로 지정해줘야 한다. 즉, 2번 변경해야 한다.
• 하지만 위의 경우, location→next = tempPtr 를 통해 포인터 하나만 변경해준다. 왜 그럴까?
• • &location → 포인터의 주소를 말한다.
• location→next가 파라미터로 들어가고, location→next에 new로 동적할당을 받기 때문에 새로 생긴 노드가 new, new의 이전 노드가 prev라면 prev→next가 이미 new를 가리키고 있게 된다.

template <class ItemType>
void Delete(NodeType<ItemType>* &location, ItemType item){
	if(item == location->info)) {
		NodeType<ItemType>* tempPtr = location;
		location = location->next;
		delete tempPtr;
	}
	else
		Delete(location->next, item);
}
 
template <class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item){
	Delete(listData, item);
}

• Tail Recursion : 함수의 마지막 줄에 재귀 호출이 포함된 구조
• Tail Recursion은 반복문으로 쉽게 대체할 수 있다.
• 재귀 호출은 함수의 파라미터와 지역 변수를 저장해야 하기 때문에 activation record로 지니고 있어야 한다. 하지만 Tail Recursion은 맨 마지막에 재귀 호출을 하고 그 이후 동작이 없기 때문에 이를 저장할 필요가 없어 반복문으로 변경하기 쉽다.
• Tail Recursion은 하나의 반복문으로 변환할 수 있다.

Recursion vs. Iteration

• 반복문 : looping 구조를 사용한다.

• 재귀문 : branching 구조를 사용한다.

• 재귀는 시간, 공간 측면에서 반복문보다 비효율적이다.

• 하지만 문제를 간단하게, 직관적으로 풀 수 있고 코드를 쉽게 이해할 수 있다.

• Combination과 같은 경우 중복되는 계산이 많이 발생하는데 다음과 같은 경우 중복값을 저장해 사용하는 memoization 방식을 사용하여 중복을 줄인다.

• 재귀의 사용 시점

• 재귀 호출의 깊이가 문제의 크기에 비해 상대적으로 얕을 경우

• 재귀가 비재귀적 방식과 비슷한 복잡도를 가질 경

• 재귀가 비재귀적 방식보다 더 짧고 간단한 경우