[백준 | 파이썬3] 10872. 팩토리얼 - 재귀

https://www.acmicpc.net/problem/10872

 

10872번: 팩토리얼

> 재귀함수

 

반복문을 활용해 풀었던 문제인데, 이번에는 재귀 함수로 해당 문제를 다시 풀어보았다. 

아래 코드처럼 코드를 작성하여 제출했더니 RecursionError가 떴다. 

 

* RecursionError: 재귀와 관련된 에러로 파이썬이 정한 최대 재귀 깊이 보다 그 깊이가 더 깊어질 때 발생하는 에러이다. 백준 채점 서버에서 최대 재귀 깊이는 1,000으로 설정되어있다. 

 

* 해당 코드에서 RecursionError가 발생한 이유: fac(5)인 경우를 생각해보자. 5*4*3*2*fac(1)까지 함수가 작동했을 때,  if i==1: 에서 1을 return하면 함수가 그 자리에서 종료되기 때문에 recursionerror없이 코드가 잘 돌아간다. 그러나 fac(0)인 경우엔 if i==1: 이 0은 잡아줄 수 없다. 따라서 0*-1*-2*fac(-3)... 으로 계속해서 함수가 호출되기 때문에 재귀 오류가 발생한다. 그러므로 i==1 코드를 i<=1 혹은 i==0으로 바꿔 작성하면 오류가 발생하지 않는다. 

 

 

 ▶ RecursionError가 발생하는 일반적인 이유: fac함수는 한번 호출될 때 총 n+1번의 재귀 호출이 발생하므로 print(fac(n))의 재귀 깊이는 n+2가 된다. 따라서 n이 997이하인 경우에는 해당 에러가 발생하지 않지만, 998이상인 경우엔 재귀 깊이가 최대 재귀 깊이인 1000이 되어 해당 에러가 발생한다.

 

 

▷Recursion Error을 해결하기 위한 방법으로는 두 가지가 있다. 

 

첫 번째, 재귀가 아닌 반복문을 활용해 문제를 푸는 것이다. 

 

두 번째, 시스템 최대 깊이를 늘려주는 것이다. sys.setrecursionlimit()을 사용하여 최대 재귀 깊이를 늘려주면 에러 없이 실행할 수 있다. 

---

(* 포스팅 오류 지적해주신 코딩님 감사합니다!)