간단한 재귀 알고리즘

재귀 알고리즘?

간단히 말해 자신을 정의할 때 자신을 호출하는 방법이다.

• 팩토리얼을 구하는 간단한 재귀 함수를 정의해보자.

def factorial(n):
  if n <= 1:
    return 1

  return n * factorial(n-1)

심플하다.

5!을 구한다고 생각해보자.

factorial(5) = 5 x factorial(4)
factorial(4) = 4 x factorial(3)
factorial(3) = 3 x factorial(2)
factorial(2) = 2 x factorial(1)
factorial(1) = 1

이렇게 n 값을 1씩 빼주면서 자신을 호출하는 과정을 통해 5x4x3x2x1 을 구할 수 있다.
물론 n 값이 1보다 작으면 안되니까 n 값이 1 이하이면 1을 리턴해주면 된다.

재귀함수를 쓸 때 상황에 맞는 스토퍼를 정해주자.