Recursive Solutions

생성일: 2021년 11월 7일 오후 5:28

Factorial 함수

RecursiveSolutions.h

//Factorial 팩토리얼 함수
int Factorial(int number)
{
	if (number == 0) //base case
		return 1;
	else    //general case
		return number * Factorial(number - 1);
}

Combinations(조합) 함수

//Combinations 조합 함수
int Combinations(int n, int k)
{
	if (k == 1)	//base case 1
		return n;
	else if (n == k) //base case 2
		return 1;
	else  //general case
		return (Combinations(n - 1, k) + Combinations(n - 1, k - 1));
}

Power 함수

//Power 제곱 함수
int Power(int x, int n)
{
	if (n == 0)  //base case
		return 1;
	else  //general case
		return (x * Power(x, n - 1));
}

곱셈 함수(Multiplier)

//곱셈 함수 a*b 리턴
int Func(int a, int b)
{
	int result;
	if (b == 0)
		result = 0;
	else if (b > 0)
		result = a + Func(a, b - 1);
	else
		result = Func(-a, -b);

	return result;
}

UnsortedListType 에서의 Recursion

unsorted.h

//Unsorted list 안에 value가 있는지 확인하는 함수
bool UnsortedType::ValueInList(ItemType value, int startIndex)
{
    if (info[startIndex] == value)
        return true;
    else if (startIndex == length - 1)
        return false;
    else
        return ValueInList(value, startIndex + 1);
}

ItemType.h에서 연산자 오버로딩을 통해 ==이 ItemType의 value가 같은지를 판단하는 기능을 수행함.

계속해서 list의 첫번째 인덱스의 아이템이 찾는 아이템인지 확인하고 아니면 다음 인덱스를 확인하는 형식

Linked Sorted List 에서의 Recursion

SortedType.h

리스트의 마지막 아이템부터 출력하는 함수인 RevPrint 구현

template <class ItemType>
void SortedType<ItemType>::RevPrint(NodeType<ItemType>* listPtr)
{
	if (listPtr == NULL) //base case
		return;
	else   //general case
	{
		RevPrint(listPtr->next);
		std::cout << listPtr->info << std::endl;
	}
}

template <class ItemType>
void SortedType<ItemType>::Print()
{
	NodeType<ItemType>* listPtr;
	listPtr = listData;
	RevPrint(listPtr);
}

재귀를 이용한 Insert 함수 구현

template <class ItemType>
void SortedType<ItemType>::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, item);  //location->next 가 레퍼런스로 받아지기 때문에 앞의 노드와 자동으로 연결되는 것이 가능해짐
	}
}

template <class ItemType>
void SortedType<ItemType>::InsertItemWithRecursion(ItemType newItem)
{
	Insert(listData, newItem);
}

여기서 중요한 점은 재귀를 사용하지 않고 insert함수를 구현할 때에는 predLoc를 이용해 새롭게 넣을 노드의 앞 노드를 가리키고 있다가 둘을 이어주는 작업을 별도로 해줬어야 한다. 하지만 재귀를 이용해 구현한다면 위처럼 레퍼런스로 파라미터인 location을 받아오고 location→next를 전달해 주기 때문에 location = location→next 처럼 작동하고 location = new NodeType<ItemType>; 이 작동 할 때 저절로 이전의 노드와 새롭게 넣을 노드가 연결된다.

재귀를 이용한 Delete 함수 구현

//Delete 함수 (재귀)
template <class ItemType>
void SortedType<ItemType>::Delete(NodeType<ItemType>*& location, ItemType item) //레퍼런스로 받아와야 자동 연결 가능
{
	if (item == location->info)
	{
		NodeType<ItemType>* tempPtr = location;
		location = location->next;  //여기서 앞의 노드와 뒤의 노드 자동 연결
		delete tempPtr;
	}
	else
		Delete(location->next, item); //location->next 가 레퍼런스로 받아지기 때문에 앞의 노드와 뒤의 노드가 자동으로 연결되는 것이 가능해짐
}

template <class ItemType>
void SortedType<ItemType>::DeleteItemWithRecursion(ItemType item)
{
	Delete(listData, item);
}

Insert와 마찬가지로 삭제된 노드의 앞과 뒤의 노드가 자동 연결 됨

Array로 구현된 Sorted List에서의 Recursion

Sorted.h

리스트안에 해당 아이템이 있는지 찾는 바이너리 서치 함수 구현

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

ItemType의 연산자 오버로딩이 구현되어 있어야한다.