자료구조 - Recursion(재귀)

재귀라는 것은 메서드를 호출할 때 호출 하는 것과 호출당하는 것이 동일한 것을 의미한다.

 

이때 직접적으로 호출되지 않더라도 호출을 계속하다 보니 다시 호출되는 경우도 재귀의 한 종류로 Indirect recursion이라고 한다.

 

예를 들어 f라는 함수에서 g를 호출하고 g에서 h를 호출한 다음 h에서 f를 호출하는 경우를 Indirect recursion의 한 종류로 볼 수 있다.

 

컴퓨터 언어에 따라 recursion을 사용할 수 없는 언어도 있는데 대표적으로 Fortran이 있다.

 

이러한 경우는 모든 재귀는 루프를 통해 표현할 수 있다는 점을 이용해서 for나 while문으로 루프를 사용해야 한다.

 

재귀는 일반적으로 효율성이 떨어진다.

 

그 이유를 살펴보면 재귀는 기본적으로 실행하면 함수를 호출 했을 때 그 함수가 끝나면 다시 지금의 위치로 돌아와서 나머지 과정을 수행해야한다.

 

따라서 재귀함수가 어디로 돌아가야하는지 retrun address를 항상 가지고 있어야 한다.

 

그리고 재귀는 기본적으로 선입선출 과정을 따르기 때문에 stack을 통해서 관리하는데 재귀를 수행할 때 사용하는 메모리가 모두 동일한 경우는 문제가 없지만 Indirect recursion과 같은 경우에는 호출된 값이 차지하는 메모리의 크기가 서로 다르다.

 

따라서 stack에서 함수를 처리한 후 pop을 처리할 때 얼마만큼의 메모리를 제거해야할지의 정보도 따로 저장해야한다.

 

그렇기 때문에 재귀가 실행 될 때마다 돌아갈 주소 저장, 제거할 메모리 크기, 입력될 파라미터 복사등의 처리해야할 부분이 많아 재귀를 할 때마다 계속 메모리를 잡고 있어야 하여 메모리를 많이 차지한다는 단점이 있다.

 

다만 재귀를 사용함으로써 코드가 단순해지고, 더 직관적이기 때문에 읽기 쉬워져 다른 사람이 쓴 코드를 해석할 때 혹은 내가 나중에 다시 코드를 볼 때 유용하다는 장점이 있다.

 

재귀를 사용할 때 가장 중요한 것은 재귀를 끝낼 수 있는 base case를 설정하는 것이다.

 

왜냐하면 base case가 없으면 기본적으로 재귀는 무한히 반복되기 때문에 반복이 언제 멈출지 정하는게 중요하기 때문이다.

 

재귀함수가 잘 동작하는지 평가하는 방법은 다음과 같이 3가지가 있다.

 

1. base case가 잘 만들어졌는가?

    base case를 제대로 만들지 않으면 재귀의 마지막 종료조건이 없어 무한하게 반복하기 때문이다.

 

2. recursion을 실행했을 때 처음보다 작은 범위에서 다루게 되는가?

    만약 재귀를 할 때 동작 할 때 마다 다루는 범위가 같거나 크게 된다면 멈추지 않고 무한하게 반복하기 때문이다.

 

3. 일반적은 경우에 대해서 잘 동작하는가?

    재귀를 사용할 때 호출을 정확히 하였는지, 혹은 우리가 생각한 형태로 재귀가 실행되는지 확인해야한다.