[Swift] 백준 10872번 팩토리얼

문제 출처: 백준 10872번 팩토리얼

문제

---

풀이

---

주어진 수의 팩토리얼 값을 구하는 문제로 5! (팩토리얼)은 5 X 4 X 3 X 2 X 1 = 120입니다. 이 공식을 재귀함수를 이용해 풀어보겠습니다.

/// 팩토리얼 함수
func factorial(N: Int) -> Int {
  if N <= 1 {
    return 1
  }

  // 재귀
  return N * factorial(N: N - 1)
}

// 결과 출력
print(factorial(N: Int(readLine()!)!))

1. 입력받은 값을 Int 형으로 변환한 뒤 팩토리얼 함수를 호출해 정답을 출력합니다.

재귀 함수의 경우 무한 호출 구조에 빠질 수 있으므로 if 문과 같이 재귀를 중단할 조건이 필요합니다.
return 부분에 함수를 호출하면서 반복문의 역할을 하게 되는데요.

팩토리얼 연산을 일반 반복문으로 짜게 되면

func factorial(N: Int) -> Int {
  var result = 1
  for i in 2...N {
    result *= i
  }
  return result
}

• 이런 식으로 함수를 호출해 1부터 인자값 범위에 있는 자연수를 곱한 값을 리턴합니다.
• 5를 예로 계산하면 factorial(N: 5) -> (((result * 2) * 3) * 4) * 5가 됩니다.

재귀함수의 장점으로는 반복문처럼 result라는 값을 저장할 변수를 추가로 만들지 않아도 되고 좀 더 간결하게 코드를 짤 수 있습니다.
단점도 있는데요…함수를 반복 호출할 때마다 메모리에 올라가게 되면서 반복문보다 메모리를 더 많이 사용합니다. 예를 들면 팩토리얼 함수의 return 부분을 식으로 나타내면

• factorial(N: 5) = 4 * factorial(N: 3)
  　　　　　　　　　　↪︎ 3 * factorial(N: 2)
  　　　　　　　　　　　　　↪︎ 2 * factorial(N: 1)

이렇게 표현이 되는데요 factorial(N: 1)부분에서 값이 return 되지 전까지 factorial(N: 5)의 함수가 종료되지 않기 때문입니다.

이러한 단점을 해결하기 위해 꼬리재귀라는 방식이 있다고 합니다.
반복 호출시 값을 기다리지 않고 바로 값을 리턴하는 형태 인데요.

func factorial(N: Int, total: Int) -> Int {
  if N <= 1 {
    return total
  }
    
  return factorial(N: N - 1, total: N * total)
}

이렇게 결과 값을 인자값으로 넘겨주게 되면 호출한 함수는 자기 자신을 호출하고 바로 종료가 됩니다.

이렇게 풀 경우 메모리: 69104 KB, 시간: 24 ms 결과가 나오게 됩니다.