재귀 함수를 쓰는 이유

자료구조와 알고리즘에 대해 잘 알고있는가?

위 질문에 자신이 없어 최근 다시 책을 펴서 공부하고 있다.
재귀 함수 part가 나와 갑자기 궁금해서 검색을 해보았다.

재귀 함수는 왜 쓰는가?

몇 개의 글을 쭉 보던 중 누군가의 댓글에 꺠달음을 얻고 정리한다.
링크 : https://kldp.org/node/134556

재귀함수를 쓰는 이유
- 1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때. (가독성 이야기)
- 2. 변수 사용을 줄여 준다.

1번은 알고 있었던 내용이나, 2번에 대한 설명은 오! 라는 감탄사를 가져다 주었다.

변수 사용을 줄여준다는건 변수가 잡는 메모리에 대한 이야기가 아니라,
mutable state (변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기다.

함수형 프로그래밍에서, 함수를 일급 객체로 취급하여 함수를 인자로 전달 및 반환하여
mutable state 상태를 제거하는 것 처럼...


그리고 링크된 글에는 이러한 말이 나온다.

tail recursion (꼬리 재귀)

위에서 재귀 함수를 사용하는 이유, 즉 장점을 설명했는데 왜 재귀를 자주 쓰지 않을까?
재귀 함수는 장점만큼 단점도 크다

재귀함수를 쓰지 않는 이유는 메모리를 많이 차지하며 성능이 반복문에 비해 느리다.

함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.

재귀함수를 쓰게되면, 함수를 반복적으로 호출하므로, 스택 메모리가 커지고,  호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있다.

또한 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 들어 성능도 느려진다.

다시 원점으로 돌아가서, 꼬리 재귀는 기존 재귀의 위와 같은 문제점을 해결할 수 있는 방법이다. 결론적으로 꼬리 재귀의 장점을 얻으려면 2가지가 필요하다

1. 프로그래머가 재귀를 꼬리 재귀 방식으로 개발한다.
2. 컴파일러가 꼬리 재귀 최적화를 지원해야 한다.

컴파일러가 꼬리 재귀 최적화를 지원하지 않으면, 개발자가 꼬리 재귀 방식으로 개발해도 성능 및 메모리의 이점을 얻을 수 없다.

코드적으로 보면 재귀와 꼬리재귀는 다음과 같은 형태를 가진다.

int Recursive(int n) 
{
 if(n==1) return 1;
 return n + Recursive(n-1);
}

int Tail_Recursive(int n, int acc)
{
 if(n==1) return acc;
 return Tail_Recursive(n-1, n + acc );
}

차이를 알겠는가? 일반 재귀는 함수의 마지막, return에 연산이 필요하다. (n + 함수(n-1))
꼬리 재귀는 return에 연산이 필요없다. 매개변수로 필요한 연산을 전달한다. (함수(n-1, n+acc))

여기서부터 꼬리 재귀의 이점은 컴파일러가 지원한다. 컴파일러가 꼬리 재귀를 최적화 할 수 있으면 최적화 하는 과정에서 꼬리 재귀를 반복문으로 변경한다.
따라서 기존 재귀의 문제였던 메모리와 성능에 대한 문제가 제거되는 것이다.