[백준] (Swift) 10872번: 팩토리얼 (재귀 vs 반복)

📌 문제

10872번: 팩토리얼

 

📌 풀이 개요

N에서 1까지 차례로 곱하는 팩토리얼은 크게 2가지 경우로 풀어 볼 수 있다.

1. 재귀적으로(recursively) 푸는 방식이거나,
2. 반복적으로(iteratively) 푸는 방식이다.

 

📌 풀이 1: 재귀함수

재귀에 대한 개념은 아래의 링크 페이지에 정리해 두었다.

[알고리즘] 재귀(Recursion)와 콜 스택(Call Stack)

 

재귀함수로 푸는 방식은 아래와 같다.

1. 팩토리얼에 대한 함수를 정의해야 한다. → $\mathrm{factorial}(n)$
2. 함수에서 반환해야 하는 결괏값을 1로 먼저 할당한다.
3. 종료 조건(base case)으로 인수가 1일 때, 1을 반환한다. → $\mathrm{factorial}(n)$
4. 재귀 단계(recursive step)에서는, 현재 인수와 인수에서 1을 뺀 재귀 함수를 곱하여 결괏값에 대입한다 → $n \times \mathrm{factorial}(n-1)$
5. 4번의 재귀 단계는 3번의 종료 조건에 닿을 때까지, $n \times \mathrm{factorial}(n-1)$를 차례대로 수행해 나가며 재귀 함수를 계속 호출한다.
6. 종료 조건이 닿으면 결괏값을 반환하고. 5번의 재귀 단계를 반대 순서로 호출된 재귀함수를 계속 반환한다.
7. 함수의 결괏값을 최종적으로 반환한다.

 

📌 코드 1 : 재귀함수

이제 정의한 함수에 실제로 입력받은 값을 대입하여 이를 화면 출력한다.

// 입력 받은 문자열을 상수 N에 할당
let N = Int(readLine()!)!

// 팩토리얼 함수 정의
func factorial(_ n: Int) -> Int {
    var result = 1  // 결괏값을 1로 초기화

    if (n <= 1) {
        return 1 // 매개변수가 1 이하일 경우 1을 반환
    }
    else {
       result = n * factorial(n - 1) // 매개변수가 1 초과면 재귀함수 실행
    }

    return result // 결괏값 반환
}

// 팩토리얼 함수의 인수로 할당 받은 N을 입력하여 결괏값 화면 출력
print(factorial(N))

 

📌 풀이 2 : Swift의 stride() 메서드

이번에는 재귀가 아닌 반복적으로 푸는 방식이다. Swift의 내장 메서드 중 하나인 stride()를 이용하면 수를 단계적으로 나타낼 수 있다.

 

stride()에 대한 개념은 아래의 링크 페이지에 다루었다.

[Swift] stride()로 숫자를 단계적으로 다루기

 

stride()로 푸는 방식은 아래와 같다.

1. 결괏값을 1로 할당한다.
2. stride()를 이용하여 N부터 1까지(0 직전까지) 차례대로 result에 값을 곱한다.
3. 결괏값을 반환한다.

 

📌 코드 2 : Swift의 stride()를 이용

// 입력 받은 문자열을 상수 N에 할당
let N = Int(readLine()!)!

// 결괏값에 1을 할당
var result = 1

// stride를 이용하여 N부터 0의 직전까지 result에 값을 곱하여 대입
for i in stride(from: N, to: 0, by: -1) {
   result *= i
}

// 최종으로 곱해진 값을 화면 출력
print(result)

 

📌 후기

• 이처럼, 팩토리얼을 재귀적으로(recursively) 또는 반복적으로(iteratively) 문제를 풀어 보았다.
• 전에 배운 재귀의 개념을 내용을 실제 Swift 언어로 응용할 수 있어서 좋았다.
• 반복적인 단계를 다룰 때 stride() 메서드를 처음 사용해 보는 계기가 되었다.