자바 Factorial stackoverflow 궁금증

Question

안녕하세요.java 언어로 Factorial을 간단하게 재귀 함수로 코딩하면숫자가 큰 경우 스택오버플로우가 발생합니다. 이 재귀 함수를 반복문으로 바꾸는 방법 말고,즉, 재귀 함수를 사용하면서 Factorial을 구현할 때 스택 오버 플로우를 막을 수 있는 방법이 있나요 ?? P.S꼬리 재귀라는 것이 있던데.. 이게 자바에서 적용이 되는건지 궁금합니다.인터넷 코드를 그대로 작성하여 돌려보면 작동하지 않아서요...컴파일러 최적화 설정을 해야한다는 글도 있구요.

aeba · Accepted Answer

꼬리재귀 최적화는 정말 옛날부터 알려진 기법이지만 javac에서는 단순히 for/while문의 루프가 선호된다는 이유로 구현되지 않은 것일 뿐입니다. 일반적인 의미*로 자바에서 재귀함수로 팩토리얼 함수를 짜면 스택 오버플로가 발생하지 않을 것이라고 장담할 수 있는 방법은 javap로 바이트코드를 직접 읽고 꼬리재귀 최적화가 되어 있는 것을 눈으로 확인하는 수밖에 없습니다. 함수형 프로그래밍을 지원하면서 같은 자바 가상머신에서 돌아가는 다른 언어들 (예: 스칼라, 클로저 등)은 스택오버플로를 막는 기능 (스칼라에서는 &#64;tailrec 어노테이션, 클로저에서는 recur 키워드)가 제공됩니다. 전 재귀만 쓰고 루프는 거의 쓰지 않습니다만, 어쨌든 제 추천은 자바에서는 가능한 한 재귀를 쓰지 않고 (특히 꼬리재귀로 가능한 것들은 확실히 루프로도 가능하기 때문에) 루프를 쓰는 것입니다. 어떤 언어를 쓸땐 그 언어의 철학과 대세에 따르는게 가장 좋습니다. 그래야 다른 사람이 읽어도 위화감이 없고 이해가 빨리 됩니다. * 일반적이지 않은 의미로, 트램폴린이라는 기법으로 스택이 아니라 힙에 계산결과를 쌓아서 스택 오버플로를 피하는 재귀 테크닉이 존재합니다.

NortonSimon · Answer

우선 tail recursion optimization은 optimization이기 때문에 구현하고 말고는 순전히 JVM 및 java compiler (java to bytecode) 마음입니다. tail recursion은 tail call의 특수예인데, caller와 callee가 동일할 경우 tail recursion이라고 부릅니다. JAVA는 tail call을 구현하는 게 일반적으로는 불가능합니다. 왜냐하면 컴파일 할 때 callee의 코드를 볼 수 없거나 확신할 수 없는 경우가 있습니다. tail recursion은 javac가 callee와 caller가 같다고 확신할 수 있는 경우입니다. 이게 왜 안 되(었)느냐는 건 구현에 달린 건데, x86용 Oracle JDK/JVM에 한정해 봅시다. 그 경우에도 사실 역사적으로 왜 그 기능이 구현이 안 되었느냐는 오라클 그 팀 엔지니어도 정확히 대답하기 어려운 주제입니다. 단순히 iteration이 선호된다는 이유로 구현이 안 되었다는 건 믿기 어렵고요. 몇 가지 이유를 추려볼 수 있는데, 하나는: https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-allhttps://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all 요약하면, stack frame의 수를 security 측면에서 뭔가 할 때 정보로 삼았었기 때문이라는군요. tail recursion optimization은 stack frame의 수를 바꾸죠. Oracle에서는 tail recursion optimization보다 중요한 일이 많다고 생각하기 때문에 (2015년 당시) 아직 바꿀 계획이 없다고 했었군요. (바꿀 거지만 우선 순위가 낮다고 한 건데, 이 얘기는 지금으로서는 바꿀 계획이 별로 없다는 뜻입니다.) 별개로 factorial을 그냥 n*f(n-1) 처럼 쓰시면 tail recursion이 아닙니다. 코드를 조금 바꿔야 하고요. recursion을 무조건 피하는 게 능사는 전혀 아닙니다. 이것도 논쟁이 있긴 한데, 일반적으로 언어 무관하게 recursion으로 된 코드가 읽기 좋습니다. 문제에 따라서는 recursion이 훨씬 우아한 해법일 때도 많고요. 다만 recursion을 쓰게 되면 stack이 어디까지 늘어날 수 있고 JVM(들)이 어디까지 감당할지 이해하면서 써야겠죠.

aeba · Answer

&#64;NortonSimon전문가는 아니지만 아는만큼 답해보겠습니다.팩토리얼같이 단순한 함수에 국한해서는 단순히 iteration이 선호되기 때문에 구현이 안 된게 맞습니다. (당장의 기술적인 이슈가 없는건 아니지만, 크게 보면 우선순위의 문제가 더 강하다는 뜻입니다)넓은 의미의 tail recursion(mutual tail recursion 등) 이나 일반적인 tail call이 아니라, 질문자님께서 말씀하신 팩토리얼 함수같은 가장 단순한 형태의 taill recursion은 그냥 컴파일러가 루프로 고쳐써주면 되기 때문에 (제가 위 답변에 JVM이 아니라 javac라고 쓴 이유입니다) VM이 관여할 이유가 없습니다. 그것은 제가 예시를 들었듯이 같은 VM에서 돌아가는 스칼라와 클로저를 보시면 알 수 있습니다. 하지만 위에 언급한 간단한 꼬리재귀를 제외한 taill recursion이나 taill call들은 현재 프레임을 제거하고 그 자리에 새로운 프레임을 쌓아야 하는데, 이게 JVM의 내부에서 문제를 일으킨다는 뜻입니다.

NortonSimon · Answer

aeba님// 저는 비교적 전문가라고 할 수 있는데요. 세 번째 문단 부터, java에 한해서 보면 jvm에서 구현될 수도 있고 javac에서 구현될 수도 있습니다. 그 역시 구현과정의 선택에 달린 문제입니다. 나머지는 무슨 말씀을 하시는지부터 이해가 잘 안 됩니다. factorial도 만약 loop으로 바꾸지 않으면 stack frame이 fact(n)을 부르면 n개 가까이 생기게 됩니다. 그러면 JAVA runtime이 그 stack frame의 개수를 셀 수 있고, 그 정보를 보안에 이용한다는 의미로 저는 제가 드린 링크를 이해했어요. loop으로 바꾸면 stack frame이 1개가 되죠? 두 번째 문단. 보통은 컴파일러 개발자, 심지어 그 팀 컴파일러 개발자 입장에서도 왜 특정 optimization이 구현 안 되었는지 역사적 이유를 알기는 어렵습니다. 가끔은 전혀 어이없는 이유인 경우도 있어요. 예를 들면 Sun Studio는 아직도 avx512의 몇몇 auto-vectorization 기능이 없는데, 그 이유가 다른 고상한 게 아니라 그냥 걔네가 쓰는 IR이 그동안 역사적으로 통하면서 일을 쉽게 해주는 희안한 가정을 하고 있었는데 그 가정이 auto-vectorization에는 적용이 안 되게 됐기 때문입니다. 다만 stack frame counting은 오라클 개발자가 직접 말한 바대로 반드시 필요한 건 아니고 좋지 않은 design decision이었지만 어쨌든 거기 있었고 그게 명백하게 어떤 종류의 tail call optimization도 불가능하게 하기는 하죠. 그것과 별개로 aeba님의 말씀은 논리적으로도 이해가 잘 안 됩니다. 정당화가 가능한 성격의 statement인지에 대한 확신 자체가 안 서요. 우선 iteration을 선호하지 않는 주체가 뭔가요? JVM인가요, JAVA를 만들고 유지하는 사람들인가요? 전자라면 당연히 최대한 많은 게 구현되어 있어야 하겠죠. 후자라면 JAVA나 JAVA standard를 정하는 핵심 엔지니어가 내놓은 디자인 가이드라도 있나요, &#34;우리 간단한 tail call도 optimize 안 해줄 거니까 iteration을 쓰세요.&#34;라고 하는? 왜 그렇게 생각하시죠?

자바 Factorial stackoverflow 궁금증

4개의 답변

Q&A 목록