algorithm- 팩토리얼 구하기와 재귀 호출

1. 재귀 호출

재귀 호출은 함수가 자기 자신을 다시 호출하는 것을 뜻한다.

즉 어떤 함수 안에서 자기 자신을 부르는 것을 말한다.

def hello():
    print("hello")
    hello() # hello()함수 안에서 다시 hello()를 호출

hello() # hello()함수를 호출

hello함수를 보면 "hello"라는 문장을 출력한 다음 자기 자신인 hello()를 다시 호출하는데

이것이 바로 재귀 호출이다.

"hello"를 출력한 후 다시 자기 자신을 호출하고 또 다시 "hello"를 출력하고 다시 자기 자신을

호출해서 "hello"를 출력하는 과정을 영원히 반복하게 된다. ( 종료 조건이 없기 때문에 )

그러다가 결국 함수 호출에 필요한 메모리를 다 써 버리고 나면 에러를 내고 정지해버린다.

그러므로 재귀 호출 프로그램이 정상적으로 작동하려면 반드시 종료 조건이 필요하다.

 

실행 결과

종료조건이 없어서 계속 재귀 호출을 반복하다가 메모리를 다 써 버리고 재귀에러가 난다.

 

 

2. 팩토리얼을 구하는 알고리즘1 (재귀 호출 미사용)

# 팩토리얼을 구하는 알고리즘1 (재귀 호출 미사용)
#입력: n
#출력: 1부터 n까지 연속한 숫자를 곱한 값

def fact(n):
    f = 1 # 곱을 계산할 변수 초기값은 1
    for i in range(1, n + 1): # 1부터 n까지 반복(n + 1은 제외)
        f = f * i
    return f

print(fact(5))
print(fact(10))

실행 결과

 

 

3. 팩토리얼을 구하는 알고리즘2 (재귀 호출 사용)

# 팩토리얼 구하는 알고리즘2 (재귀 호출 사용)
# 입력: n
# 출력: 1부터 n까지 연속한 숫자를 곱한 값

def fact2(n):
    if n <= 1: # 1이하가 되면 종료(0포함)
        return 1
    return n * fact2(n - 1) # n!을 구하기 위해서 1 작은 값인 (n - 1)이 재귀호출 됨

print(fact2(5))
print(fact2(10))

n이 1보다 크면 n x (n-1)을 결과값으로 돌려주고 이 과정에서 n!을 구하기 위해서 1작은 값인 fact(n - 1)이

재귀 호출된다.

그리고 나서 다시 종료 조건에 해당하는지 확인하고 종료 조건이 아니라면 이번에는 바로 직전 값에서 하나

더 작아진 값으로 호출하고 이렇게 계속 반복하다보면 결국 fact(1)이 되고 종료가 되어

원하는 답을 얻게 된다.

 

예) fact(5) 호출

1. fact(5)는 5 * fact(4)이므로 fact(4)를 호출하고

2. fact(4)는 4 * fact(3)이므로 fact(3)를 호출하고

3. fact(3)는 3 * fact(2)이므로 fact(2)를 호출하고

4. fact(2)는 2 * fact(1)이므로 fact(1)를 호출하고

5. fact(1)은 종료 조건이므로 더이상 fact() 함수를 호출하지 않고 1을 돌려준다.

 

5!

= 5 x 4!

= 5 x 4 x 3!

= 5 x 4 x 3 x 2!

= 5 x 4 x 3 x 2 x 1!

= 5 x 4 x 3 x 2 x 1

= 120

 

실행 결과