재귀 함수 II

---

 

III 코드로 보는 재귀함수

재귀함수의 원리는 스택의 개념이 있어야 하므로 스택의 개념을 먼저 접하고 재귀를 이해하시는 걸 추천합니다.

 

팩토리얼 예시 

5! = 5*4*3*2*1 =  120

4! = 　4*3*2*1 =  24

3! = 　　3*2*1 =  6

2! = 　　　2*1 =  2

1! =　　　　 1  = 1

 

 

 

For문으로 작성된 팩토리얼

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

print(factorial_iterative(3))

N=3일 경우, for문은 1부터 3까지 반복됩니다:

1. 첫 번째 반복 (i=1):
   • result = result * i 실행: result = 1 * 1
   • result 값은 1이 됩니다.
2. 두 번째 반복 (i=2):
   • result = result * i 실행: result = 1 * 2
   • result 값은 2가 됩니다.
3. 세 번째 반복 (i=3):
   • result = result * i 실행: result = 2 * 3
   • result 값은 6이 됩니다.

---

최종 반환 값

모든 반복이 끝난 후, factorial_iterative(3)의 결과는 6이 됩니다.

---

전체 과정 요약

• 반복 순서: i = 1 -> i = 2 -> i = 3
• 계산 과정:
  1. result = 1 * 1 = 1
  2. result = 1 * 2 = 2
  3. result = 2 * 3 = 6

결과적으로, factorial_iterative(3)의 결과는 6입니다.

 

 

 

 

 

재귀함수로 작성한 팩토리얼

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

print(factorial_recursive(3))

N=3일 경우, 함수 호출 과정을 이해하기 쉽게 설명하겠습니다.

호출된 함수를 각각 f(x), g(x), h(x)로 표현하면 다음과 같습니다:

 

1. f(x): 첫 번째 호출로, n == 3
   • n == 1이 아니므로 return n * factorial_recursive(n - 1)이 실행됩니다.
   • 이때, f(3)는 3 * g(2)로 변환됩니다.
2. g(x): 두 번째 호출로, n == 2
   • 역시 n == 1이 아니므로 return n * factorial_recursive(n - 1)이 실행됩니다.
   • 이때, g(2)는 2 * h(1)로 변환됩니다.
3. h(x): 세 번째 호출로, n == 1
   • 종료 조건이 만족되므로 return 1을 반환합니다.

---

호출 순서 및 반환 과정

호출된 함수는 재귀적으로 스택에 쌓이고, 마지막 호출이 반환된 이후에야 순차적으로 이전 호출이 계산됩니다. 따라서 호출 및 반환 과정을 정리하면 다음과 같습니다:

1. h(x): n == 1이므로 1을 반환합니다.
2. g(x): 반환된 1을 받아 2 * 1 = 2를 계산하고 반환합니다.
3. f(x): 반환된 2를 받아 3 * 2 = 6을 계산하고 반환합니다.

최종 반환 값

결과적으로 factorial_recursive(3)의 값은 6이 됩니다.

---

전체 과정 요약

• 호출 순서: f(3) -> g(2) -> h(1)
• 반환 순서: h(1) -> g(2) -> f(3)

이는 스택 구조에 의해 동작하며, 호출된 함수가 끝날 때까지 이전 함수는 대기 상태에 있다가 반환된 값을 사용하여 연산을 완료합니다.

따라서, 최종적으로 아래와 같은 흐름으로 계산할 수 있습니다:

h(1) = 1
=> g(2) = 2 * h(1) = 2 * 1 = 2
=> f(3) = 3 * g(2) = 3 * 2 = 6

결론적으로, factorial_recursive(3)의 결과는 6입니다.

 

스택과 재귀함수의 단점은 재귀함수_3에서 확인하실 수 있습니다.