7. Recursion

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

Recursion(재귀) = Loop

재귀와 반복문은 같은 것

재귀는 사실 반복문에 비해 비효율 적이지만 코드를 간결하고 가독성 있게 작성할 수 있다는 장점이 있다.

Definitions

• Base case : 재귀를 멈추는 케이스 (stated nonrecursively)
• General(recursive) case : 재귀를 진행하는 케이스 (smaller version of itself)
• Recursive algorithm : Base case + General case

팩토리얼(factorial), 조합(combinations), Power, Sort 등 다양한 함수를 재귀적으로 구현 가능

Verifying recursive functions

• Base-Case Question : 무한 루프에 빠지지 않기 위한 Base case가 제대로 존재하는가
• Smaller-Caller Question : 재귀는 원래보다 더 작은 케이스를 호출해야 함
• General-Case Question : 재귀 호출이 정확한지, 제대로 작동하는지

Linked Sorted List에서 역출력 함수

위의 형태에서 재귀를 사용하지 않고 마지막 아이템부터 출력을 하는 함수를 구현한다면 계속해서 반복문을 통해 출력하고 하는 아이템까지 접근을 해야한다.

하지만 재귀를 사용하면 마지막 아이템까지 한번 접근을 한뒤 return하면서 출력을 하고 차례대로 올라오면 된다.

Linked Sorted List에서 Insert, Delete 함수 재귀적으로 구현하기

insert 함수 작동 원리

Delete 함수 작동원리

재귀적으로 함수가 호출 될 때

각 함수의 주소를 return address에 저장하여 return 될 때 찾아갈 주소를 확보해 둔다.

이 것을 run-time stack에 저장하고 이 stack을 activation record에 배치한다.

위와 같이 스택에 Return Address와 local variable들을 저장한고 반납하면서 return된다.

여기서 Return Address인 100은 Func함수를 호출한 Main함수의 주소이다.

부가설명

• Tail Recursion
  • 재귀 호출이 함수의 제일 마지막 줄에 있는 것 ⇒ 반복문으로 변경 쉬움
  • Tail Recursion이 아니면 반복문으로 바꿀때 조심해야 한다.
  • 예시

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

    위와 같은 역출력 함수 (listPtr은 listData를 가리킨다고 가정) 를 반복문으로 구현한다면 cout해야할 listPtr→info를 어딘가에 저장해두어야 한다 ⇒ Stack 사용

    #include "StackType.h"
    
    void SortedType<ItemType>::RevPrint()
    {
    	StackType<NodeType> stack;
    	NodeType* listPtr;
    	listPtr = listData;
    	
    	while(listPtr != NULL)
    	{
    		stack.push(listPtr);  //Stack에 저장
    		listPtr = listPtr->next;
    	}
    	
    	while(!stack.IsEmpty())   //Stack에 저장된 item을 차례대로 출력
    	{
    		listPtr = stack.Top();
    		stack.Pop();
    		cout<< listPtr->info <<endl;
    	}
    }

    반복문으로 구현하면 위와 같다.
    

• 재귀 사용의 단점 및 사용처
  • 재귀를 사용한다는 것은 Divde And Conquer의 개념이다 (큰 것을 나누어서 해결하자는 관점)
  • 이 때,
    그림과 같이 같은 연산 작업을 여러번 하게 될수도 있다는 단점이 존재한다.
    
  • 따라서,

    1. Shallow Depth

    2. Efficiency

    3. Clarity

       위의 조건을 만족할 때 재귀를 사용하는 것이 바람직하다.