TIL76. CodeKata : 재귀를 사용하여 팩토리얼(factorial) 구현하기

🌈 재귀를 사용하여 팩토리얼(factorial) 구현하기

🤔 나의 Solution

재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요. 팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

✔️ n이 일이라면 1을 반환하고, 2라면 2를 반환하지만, 3일때는 6, 4일때는 24, 5일 때는 120을 반환한다.

✔️ 1!, 2!, 3!, 4!, 5! 이기 때문이다.

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

✔️ 재귀함수는 반드시 종료조건이 필요하다. 그렇지 않으면 재귀적으로 계속하여 함수를 호출하기 때문이다. 물론 재귀에 대한 제한을 걸어두었기 때문에 종료조건이 존재하지 안흔다면 에러가 발생한다.

✔️ 재귀함수로 해결할 수 있는 문제는 반복문으로 해결이 가능하다. 재귀함수와 반복문은 서로 시간복잡도는 같으나, 실제 Call Stack 과정에서 재귀호출이 속도가 느리고 메모리를 더 차지하기 때문이다.

✔️ 그렇다고해서 반복문으로 해결하는 것이 항상 좋은 결과를 가지는 것도 아니다. 반복문은 전체 로직을 서술해야하기 때문에 코드가 길어질 수 있기 때문이다. 아래 반복문으로 해결한 예시를 정리하였다.

🤔 다른 해결 방법

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result = result * i
    return result
print(factorial(5))

✔️ 간단한 팩토리얼 구현이기 때문에 코드의 길이상 크게 차이가 없지만, 복잡한 구현이라면 재귀가 더 간결하게 표현할 수 있다.

🤔 느낀점.

재귀로 풀 수 있는 문제는 반복문으로 가능하다. 서로의 장단점을 알고 사용하는게 중요하다!