(22.08.10)자료구조 2 - 재귀(Recursive)

 

재귀함수란?

재귀함수: Recursive function

재귀, 즉 직접적, 간접적으로 자기 자신을 다시 호출 하는 함수로서 탈출조건이 반드시 있어야 한다.

 

 

• 재귀함수의 기저사례
• 재귀함수의 디자인 사례
• 재귀함수를 어디에 쓸것인가?

재귀함수의 기저사례

기저사례(Base Case)란 재귀함수의 필수적인 요건으로, 무한루프를 막고 함수를 끝내기 위해 반드시 필요하다.

기저사례를 놓칠 경우 예측불가능한 결과가 도출된다.

 

 

 

재귀함수의 디자인

재귀 알고리즘으로 쉽게풀 수 있는 문제들이 있다.

대표적인 것이 바로 하노이의 타워다.

1. 직접 호출(출처:https://www.geeksforgeeks.org/recursive-functions/)

코드:

#include <bits/stdc++.h>
using namespace std;

// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole,
		char destinationPole, char auxiliaryPole)
{
	
// Base case (termination condition)
if(0 == n)
	return;

// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
	destinationPole);

// Move the remaining disk from source
// pole to destination pole
cout << "Move the disk "<< n << " from " <<
	sourcePole <<" to "<< destinationPole << endl;

// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole,
	sourcePole);
}

// Driver code
int main()
{
	tower(3, 'S', 'D', 'A');
		
	return 0;
}

// This code is contributed by SHUBHAMSINGH10

결과:

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

여기서 재귀함수의 시간 복잡도를 정의한다면

$$ M_{n} = 2M_{n-1} + 1 $$ 와 같고,

$$2^N - 1 $$ 의 시간복잡도를 갖는다.

 

2.간접 호출

void recursive(int data)
{
   static callDepth;
   
   if(callDepth > MAX_DEPTH)
      return;
 
   // Increase call depth
   callDepth++;
 
   // do other processing
   recursive(data);
 
   // do other processing
   // Decrease call depth
   callDepth--;
}

• 별도의 static 변수 depth를 통한 재귀 호출로서, 종료를 보장할 수 있다는 장점이 있다.(static count)
• 재귀 함수의 근본적 문제인 무한루프로 인한 오버플로우 위험을 감소시켜준다.
• 일반적으로, 재귀함수는 비행 컨트롤, 헬스 모니터링 시스템 등 안전 우선 어플리케이션(safety-criticl applications)에서 쓰일 수 없다.
• 하지만, 이러한 간접호출 방식은 uncontrolled calls 를 피하기 위해서 쓰인다.
• soft real-time systems에서 쓰일 수 있다. (안전 우선 어플리케이션에서는 여전히 못쓴다.)

재귀함수를 어디에 쓸 것인가?

• 장점 - 간단한 코드 구현
• 단점 - 낮은 성능, 오버플로우 가능성

-> 결국 구현하기 어려운 개념을 재귀로 하면 좋지만, 반복문 등 다른 방법으로 구현하는 것이 성능상의 이점이 더 크다.