Recursion

Recursive call

호출하는 주체 = 호출하는 객체

- Direct recursion : 자기 자신을 호출

- Indirect recursion : 다른 함수를 호출 ( f -> g -> h ...)

- 주의사항 : 무한 루프를 돌지 않도록 코드를 짜야한다.

 

some Definitions

- Base case : 재귀를 빠져나오는 경우

- General(recrusive) case : 재귀를 진행 중인 경우

- Recrusive algorithm : base case + general case 

 

Three-Question Method of verifying recursive functions

1. Base-Case Question : Is there a nonrecursive way out of the function?

2. Smaller-Caller Question : Does each recursive function call involve a smaller case  of the original problem leading to the base case?

3. General-Case Question : Assuming each recursive call works correctly, does the whole fuction work correctly?

 

EXAMPLE

(1) Factorial( n! = n*(n-1)*(n-2)...*1)

int Factorial(int num){
	if(num == 0){
    	return 1;
        }
    else{
    	return num + Factorial(num-1);
        }

 

(2) nCr ( n개 중 k개 뽑기)

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

 

(3) ValueInList(리스트 안에 찾는 값 있는지 확인)

bool ValueInList(ListType list, int value, int startIndex) {
	if(list->info[startIndex] == value)
		return true;
	else if (startIndex == list.length - 1)
 		return false;
	else
 		return ValueInList(list, startIndex - 1);
 }

 

(4) RevPrint(리스트 뒤에서부터 출력)

int RevPrint(NodeType* listPtr) {
	if(listPrt != NULL):
		RevPrint(listPtr->next);
		cout << listPtr->info << endl;
 }
 //Base case : if the list is empty, do nothing

 

(5) BinarySearch

bool BinarySearch(int info[], int item, int start, int end) {
	int mid = (start + end) / 2;
	if (start > end)                //Base case_1
		return false;
	else if (info[mid] == item)     //Base case_2
		return true;
	else {
		if (info[mid] > item) 
			BinarySearch(info, item, start, mid - 1);
		else 
			BinarySearch(info, item, mid + 1, end);
	}
}

---

Tail Recursion

 Recursive InsertItem(sorted List)

location을 참조로 받았기 때문에 location 이전 노드의 next가 가리키는 값이 자동으로 location이 된다.

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, item);
        }
        
   }
   
  template <class ItemType>
  void SortedType<ItemType>::InsertItem(ItemType newItem){
  	Insert(listData,newItem);
    }

 

 Recursive DeleteItem(sorted List)

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);
    }