20221006 TIL 꼬리에 꼬리를 무는 꼬리 재귀

오늘은 for를 이용하지 않고 코딩테스트 문제를 풀어봤다.
나는 stream api를 썼는데, 같이 공부하는 분들 중에 재귀함수로 푸신 분이 계셨다.
코드가 넘 깔끔해서 놀랐다.
그런데 첫번째 테스트 케이스만 실패를 해서 확인을 해봤더니 스택오버플로우 때문이라고 한다.
스택오버플로우가 질문 커뮤니티인 줄만 알았는데 실제로 보니 신기했다.

일반적인 재귀함수는 함수 안에서 함수가 생기고 또 생기고 또 생기니 계속 스택에 쌓이게 된다.
따라서 일반적인 재귀는 스택오버플로우가 생길 수 있는 위험성을 가지고 있다.
stream api를 쓰면 깔끔한 편이지만 for를 쓰는 것에 비해 6배 정도 느렸다...
일반적 재귀를 쓰면 빠르지만, 첫 테스트 케이스에서 스택오버플로우가 생겼다...
빠르면서 for를 안 쓰는 방법은 없을까!
홀맨님께서 해결법으로 꼬리재귀라는 키워드를 주셨다.

꼬리 재귀는 자신을 호출하는 부분에 다른 연산을 해주지 않고 자신 호출하는 부분만 딱 반환하는 방식을 말한다.
예를 들어 팩토리얼을 계산할 때 n*f(n-1) 을 반환한다면 자신을 호출하는 부분 f(n-1) 에 n을 곱하는 연산을 했기 때문에 꼬리 재귀가 아니다.
하지만 원하는 계산 값도 인자로 넘겨주게 되면
f(n-1, n*accumulator) 와 같은 방식으로 자신을 호출하는 부분에 다른 연산을 가해주지 않고 바로 자신을 반환할 수 있다.
이 방식을 사용하면 이전 함수의 컨텍스트(인자 값 및 지역 변수 등)를 다음 함수에서 더 이상 참조하지 않기 때문에 컴파일러가 꼬리 재귀 최적화를 지원한다면 스택오버플로우를 막을 수 있다.

그렇게 꼬리 재귀로 문제를 다시 풀어보았으나...

또 스택 오버플로우..
심지어 일반 재귀보다 함수 호출 횟수가 절반 정도일 때부터 스택오버플로우가 뜬다.

찾아보니 자바에서는 아직은 꼬리 재귀 최적화를 지원하지 않는다고 한다.
C++, C#, swift, Kotlin, Scala 모두 지원하는데,
자바도 계획은 있다고 하지만 아직 실현되지는 않았다..
https://www.youtube.com/watch?v=2y5Pv4yN0b0&t=1h02m18s

결과적으로는 재귀로 문제를 해결하는 것에 실패했지만, 재귀와 조금은 친해진 것 같다!

기존 방식 말고 익숙하지 않은 방식으로도 문제를 푸는 것을 시도해보자!