재귀(Recursion)

재귀란?

여러 알고리즘에 쓰이는 코딩 테크닉입니다.

분할 정복(divide-and-conquer) 전략의 기본이 되는 개념입니다.

함수가 자기 자신을 호출하는 것을 말합니다.

스택 오버플로우(Stack Overflow)

개발자들의 친구

함수는 메모리에 각자의 공간을 할당받게 되는데, 이를 호출 스택에 할당된다고 합니다.

그런데 함수가 계속해서 호출되다보면 메모리는 한정된 공간을 가지고 있으므로, 언젠가 가득차서 더 이상 함수를 호출할 수 없는 상황이 되게 됩니다.

이 때, 발생하는 에러를 스택 오버플로우라고 합니다.

재귀 함수를 작성할 때, 이 부분을 항상 염두에 두고 작성해야 하겠습니다.

그리고 이 호출 스택은 스택 자료구조를 알면 더 이해하기 쉽습니다.

그리고 호출 스택에 대한 내용은 또 글 한 편 분량이므로 다음에 다루겠습니다.

이를 해결할 수는 없을까요?

참고

이를 해결하기 위한 방법으로 꼬리 재귀(Tail-Recursion)라는 기법이 있습니다.

호출 스택에 함수 공간이 계속 쌓여서 문제가 되는 것이므로, 함수 공간이 쌓이지 않도록 하는 것입니다.

위의 사이트의 소스에서 가장 큰 변경점은 n * 에 이어지는 추가 연산을 하기 위해서 반환값이 대기를 하고 있는 상황을 추가 연산을 하지 않고 반환해주면서 스택공간이 사라지는 것을 이용합니다.

따라서 컴파일러가 최적화를 하면서 루프문으로 변경하는 것을 볼 수 있습니다.

이러한 꼬리 재귀를 이용하기 위해서는 컴파일러가 꼬리 재귀 최적화를 지원하는지 확인해야 합니다.

재귀의 성능이 안좋다는데 왜 쓸까?

재귀를 사용한다고 성능이 좋아지지는 않습니다. 오히려 반복문을 사용하는 것이 성능상으로는 더 좋은 경우가 많습니다.

그런데 왜 재귀를 사용할까요?

프로그램은 한 번 작성한다고 끝이 아닙니다. 계속 유지 보수를 해야하죠.

그런데, 반복문으로 작성된 코드는 성능상으로는 좋습니다. 하지만 재귀함수를 사용하는 것보다 읽기 불편한 경우가 존재합니다.
하지만, 재귀로 작성된 코드는 프로그래머가 읽기에 더 좋은 경우가 많습니다.

꼬리 재귀의 사례로 보았을 때, 컴파일러가 최적화를 하는 과정에서 반복문으로 바꾸는 경우도 있기 때문에, 소스 코드는 읽기 좋은 상태를 유지하는 것이 좋습니다.

그러므로, 상황에 따라서 취사 선택을 하는 것이 바람직합니다.

그리고, 대부분의 중요한 알고리즘들이 재귀를 사용하므로 개념을 잘 이해하는 것이 중요합니다.

기본 단계(Base case)와 재귀 단계(Recursive case)

재귀 함수는 자기 자신을 호출하기 때문에 무한 루프를 방지해야 합니다.

이를 방지하기 위한 부분을 기본 단계라고 합니다. 그리고 함수가 자기 자신을 호출하는 부분을 재귀 단계라고 합니다.

감사합니다.