[Python] 파이썬 팩토리얼 구현 예제 (반복, 재귀(순환))

파이썬 팩토리얼 구현 예제 (반복, 재귀)

 

팩토리얼 구현 시 2가지 방법이 있다.

1. 반복 (iterative)

2. 재귀 (recursive) (순환 이라고도 부름) 

 

둘의 차이점을 알아보자.

 

 

1. 반복 구조 팩토리얼 예제

우리가 알고있는 팩토리얼의 기본적인 형태를 반복 구조 팩토리얼이라고 한다.

예제도 for문을 이용해 팩토리얼 값을 구한다.

 4! = 1 x 2 x 3 x 4 = 24

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

print(factorial_i(4))

 

결과

24

 

 

---

 

2. 재귀(순환) 구조 팩토리얼 예제

재귀(순환)는 반복문 대신 자기 자신 함수를 호출하는 구조다.

n이 0 이 될때까지 factorial_r 함수를 계속 호출해서 팩토리얼 값을 구한다.

자기 자신을 호출하는 함수를 재귀함수라고 부른다.

def factorial_r(n):
    if n == 0:
        return 1
    else:
        return n * factorial_r(n - 1)

print(factorial_r(4))

 

결과

24

 

재귀함수에 대해 설명하기 참 애매해서 풀어 쓰자면

factorial_r 함수가 호출 될 때마다 n 값이 스택으로 값이 저장된다.

이걸 순서도로 나타내면

1. n = 4 이 될때 스택에 삽입

4

 

2. factoria_r(n - 1) 재귀함수 호출

3. n = 3 이되고 스택에 삽입

3

4

 

4. factoria_r(n - 1) 재귀함수 호출

5. n = 2 이되고 스택에 삽입

2

3

4

 

6. factoria_r(n - 1) 재귀함수 호출

7. n = 1 이되고 스택에 삽입.

 

결국 스택에는 아래와 같은 순서로 데이터가 저장된다.

1

2

3

4

 

n = 0 이 됐을 때 저장된 데이터를 pop 하면서 계산한다.

스택은 알다시피 선입후출이다.

8. 1 pop -> n = 1

2

3

4

 

9. 2 pop -> n = 1 X 2

3

4

 

10. 3 pop -> n = 1 X 2 X 3

4

 

11. 4 pop -> n = 1 x 2 x 3 x 4

 

따라서 결국 n = 24라는 값이 return 된다.