Algorithm - 재귀 호출(Recursive Call)

1. 재귀 호출(recursive call)

- 재귀 호출이란, 함수 안에서 해당 함수가 호출되는 형태를 말한다. 

- 고급 알고리즘을 이해하기 위해 반드시 이해해야 하는 개념이다.

 

 

1) 팩토리얼 알고리즘을 재귀호출을 이용하여 구현

 

a) 간단한 경우부터 생각해보기
  * 2! = 1 X 2
  * 3! = 1 X 2 X 3
  * 4! = 1 X 2 X 3 X 4 = 4 X 3!

b) 규칙이 보임: n! = n X (n - 1)!

1. 함수를 하나 만든다.
2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)

3. 함수(n) 은 n = 1 이면 return n

c) 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)

1. 먼저 2! 부터 

- 함수(2) 이면, 2 > 1 이므로 2 X 함수(1)

- 함수(1) 은 1 이므로, return 2 X 1 = 2 맞다!

 

2. 먼저 3! 부터 
- 함수(3) 이면, 3 > 1 이므로 3 X 함수(2)
- 함수(2) 는 결국 1번에 의해 2! 이므로, return 2 X 1 = 2 
- 3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞다!

 

3. 먼저 4! 부터
- 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
- 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6 
- 4 X 함수(3) = 4 X 6 = 24 맞다! 

 

 

2) 코드구현

def factorial(num):
    if num > 1:
        return num * factorial(num-1)
    else:
        return num

 

[테스트 및 결과]

---

2. 재귀호출의 패턴

 

a) 재귀호출의 패턴 - 1

# 일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

 

 

패턴 - 1의 예시)

def factorial(num):
    if num > 1:
        return num * factorial(num-1)
    else:
        return num

 

 

b) 재귀호출의 패턴 - 2 (패턴 - 1의 반대) 

# 일반적인 형태2
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

 

 

패턴 - 2의 예시)

def factorial(num):
    if num <= 1:
        return num 
    return num * factorial(num-1)

 

 

[패턴 2의 테스트 결과]

---

3. 재귀호출은 Stack의 전형적인 구조다. 

- 아래의 사진은 Stack이 작동하는 방식을 표현한 것이다. 재귀호출도 이와 같은 원리로 동작된다는 것을 알아두자.

*참고 - 파이썬에서는 1000회 이하의 재귀함수가 호출될 수 있다. 이 말은 파이썬이 재귀함수 1000회 호출 만큼의 stack 공간을 제한하고 있다는 의미이다.