[알고리즘 문제풀이] 코드카타 11 (feat. 재귀 함수)

재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요.

코드

def factorial(n):
  if n == 0 or n == 1:
    return 1
  return n * factorial(n-1)

리팩토링

def factorial(n):
  return n * factorial(n-1) if n > 1 else 1

• n이 0이거나 1이라는 것은 결국에는 1 이하일 때 1을 반환해야한다는 뜻이다. 굳이 or를 쓸 필요없다.
• n > 1일때는 n * factorial(n-1)을, 그렇지 않을 때는 1을 반환하도록 삼항 연산자를 썼다.

재귀함수에 대하여

재귀 함수란 함수내에서 자기 자신을 또 호출하는 함수를 말한다.

함수 내에서 자기 자신을 호출하기 때문에 무한 루프에 빠질수 있으므로 반드시 종료 시점을 지정해야한다.

위의 문제로 재귀 함수의 동작을 살펴보자. (가독성을 위해 조금 수정하였다.)

def factorial(n):
  if n <= 1:
    return 1
  print(n)
  return n * factorial(n-1)
  
 factorial(3)

위의 코드를 실행하면 다음과 같이 동작할 것이다.

3
2
1

처음에 3이 입력된 후 함수 내에서 factorial(2)가 실행된다.

factorial(2)에서는 factorial(1)을 호출한다.

factorial(1)에서는 n이 1이므로 1을 리턴하고 함수가 마무리 된다.

재귀함수를 사용하지 않으면 코드는 다음과 같을 것이다.

def factorial(n):
   result = 1
   while n > 1:
     result *= n
     n -= 1
   return result

재귀 함수를 사용하면 함수를 더 간략하게 작성할 수 있으나 컴퓨터에 부하가 커질 수 있다.

RecursionError

위에서 재귀함수는 항상 종료시점을 지정해줘야한다고 언급했다.

그렇다면 종료시점이 지정되지 않으면 어떤일이 발생할까?

def factorial(n):
  return n * factorial(n-1)
  
factorial(3)

위와 같은 코드가 있다고 하자.

3, 2, 1, 0, -1, -2, ... 처럼 계속하여 자신을 호출하여 무한 루프에 빠져 RecursionError가 발생한다.

RecursionError란 파이썬에서 지정한 재귀 호출 깊이보다 더 깊어졌을 때 발생한다.

sys.getrecursionlimit() 으로도 확인할 수 있듯이 파이썬에서는 재귀의 깊이가 1000으로 지정되어 있어, 이 이상 실행될 경우 에러가 발생한다.

만약 1000보다 더 재귀 호출을 해야할 경우에는 sys.setrecursionlimit(10**9)와 같이 재귀 깊이를 별도로 설정해 줄 수 있다.

하지만 깊이 제한을 너무 크게 설정해놓았거나 너무 작게 설정해 놓았을 때도 여전히 RecursionError가 발생할 수 있다.

참고
RecursionError