재귀 함수(Recursive Function)

• 자기 자신을 다시 호출하는 함수를 의미
• DFS, BFS에서 많이 사용함
• 무한히 재귀 함수를 반복하면 어느정도 출력하다 최대 재귀 깊이 초과 메시지 출력됨
  • RecursionError: maximum recursion depth exceeded while calling a Python object
  • 추가 설명
    실제로 컴퓨터 시스템 상에서 함수가 재귀적으로 호출되면 컴퓨터 시스템의 스택 프레임에 함수가 반복적으로 쌓여서
    가장 마지막에 호출된 함수가 처리가 된 이후에 그 함수를 불렀던 함수까지 처리되는 방식임
    실제로는 스택과 같은 형태로 동작한다고 이해할 수 있음
    즉, 일종의 스택 자료 구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가게 된다고 이해할 수 있음
    당연히 컴퓨터의 메모리는 한정된 크기만큼의 자원을 가지고 있기 때문에 그냥 무작정 함수가 종료되지 않고 계속해서 쌓아 올려서 재귀적으로 호출만 하게 되면 빠르게 메모리가 가득 차서 문제가 발생할 수 있어 이와 같은 재귀 깊이 제한을 걸어 둘 수가 있는 것
  • 만약 제한 없이 재귀 함수를 호출하고자 한다면 재귀 제한을 느슨하게 하거나 스택 객체를 따로 만들어서 이용하기도 함.
• 의도적으로 무한루프를 이용하는게 아니라면 재귀 함수 문제풀이에서는 반드시 종료 조건을 명시해야함

def wait_100(i) :
    if i == 100 :
        return
    print(f"{i}번째 재귀 함수에서 {i+1}번째 재귀 함수를 호출합니다.")
    wait_100(i+1)
    
    # i가 100이 되면 함수들이 차례대로 return되어 나옴 like 스택
    print(f"{i}번째 재귀 함수 종료")

wait_100(1)

 

• 재귀 함수 사용시 유의사항
  • 재귀 함수를 잘 활용하면 수학적 점화식이나 복잡한 알고리즘을 간단하게 작성할 수 있음
  • 근데 다른 사람에게 오히려 어려워 보일 수 있음
  • 모든 재귀 함수는 반복문으로 동일하게 구현 가능하고, 그 반대도 성립함
  • 근데 재귀 함수가 반복문 보다 유리한 경우도 있고 불리한 경우도 있으니 주의
  • 재귀 함수 연속 호출 시 컴퓨터 메모리 내부 스택 프레임에 쌓임.
    그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

---

[팩토리얼 구현 예제]

$n! = 1 \times 2 \times 3 \times ...  \times (n-1)  \times n$

# 반복문으로 구현한 팩토리얼
def factorial_iterative(n) :
    result = 1
    for i in range(n) :
        result *= (i+1)
    return result

# 재귀함수로 구현한 팩토리얼
def factorial_recursive(n) :
    if n <= 1 :
        return 1
    # n! = n * (n-1)!를 구현
    return n * factorial_recursive(n-1)

print(factorial_iterative(5))
print(factorial_recursive(5))

120

120

재귀 함수를 이용한 계산

5 x func(4)

      = 4 x func(3)

                = 3 x func(2)

                          = 2 x func(1)

                                    =1

---

[유클리드 호제법]

• 재귀 함수를 효과적으로 사용할 수 있는 또 다른 예시
• 최대 공약수를 구하고자 할 때 사용할 수 있는 방법
  • 최대 공약수(Greatest Common Divisor) = 두 자연수가 있을 때 공통된 약수 중 가장 큰 것

유클리드 호제법
- 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

Ex) GCD(192, 162)

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

def GCD (a, b) :
    if (a % b) == 0 :
        print(f"최대공약수는 {b}!")
        return b
    return GCD(b,a%b)

x, y = map(int,input("두 수를 입력하시오 : ").split(' '))

if x > y :
    print(f"A는 {x} B는 {y}")
    GCD(x, y)
else :
    print(f"A는 {y} B는 {x}")
    GCD(y, x)​

두 수를 입력하시오 : 162 192
A는 192 B는 162
최대공약수는 6!