재귀 함수 (Recursive Function)

• 자기 자신을 다시 호출하는 함수

def recursive():
    print("재귀함수")
    recursive()
recursive()

단 파이썬의 경우 메모리 제한이 있어서 아무제약조건 없이 재귀함수를 무한으로 돌릴수는 없다.

---

<재귀 함수의 종료 조건>

• 재귀 함수의 종료 조건을 반드시 명시해야 한다.
• 종료 조건을 명시하지 않으면 무한히 호출할 수 있다.

def recursive(i):
    if i == 100:
        return
    print("재귀함수")
    recursive(i+1)
    
recursive(1)

return 처럼 종료 조건 명시를 해야한다.

---

<재귀 함수의 예시>

1. 팩토리얼 < 1 * 2 * 3 * ...* (n-1) * n >

1.1 반복문으로 팩토리얼 구현

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

1.2 재귀적으로 팩토리얼 구현

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

---

<2. 유클리드 호제법 (최대공약수 계산)>

출처 : 이코테2021

여기서 GCD는 최대공약수를 의미하는 것이다. 즉, 192와 162 두 수의 최대공약수를 구하는 것이다.

1. 192(A)와 162(B)를 나눈 나머지 30(R)을 구할 수 있다.
2. 다시 162(A)와 30(B)을 나눈 나머지 12(R)을 구할 수 있다.
3. 다시 30(A)과 12(B)를 나눈 나머지 6(R)을 구할 수 있다.
4. 결론적으로 12와 6이 남게 된다.
5. 192와 162의 최대공약수가 12와 6의 최대공약수라고 알 수 있다.
6. 6은 12의 배수이므로 192와 162의 최대공약수는 6이란걸 알 수 있다!

 

<유클리드 호제법 예제>

• 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 한다.
• A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
    
print(gcd(192,162))

* a가 b의 배수이면 b를 반환한다.

---

<재귀 함수 사용의 유의 사항>

• 재귀 함수를 활용시 복잡한 알고리즘을 간결하게 작성할 수 있다.
• 반복문을 이용하여 동일한 기능을 구현가능
• 무조건 반복문보다 유리한 것은 아니다.
• 함수를 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓인다.