재귀호출 (recursive call)

순서

1. 재귀의 개념 및 예제

2. 꼬리재귀

---

1. 재귀의 개념 및 예제

재귀의 사전적 의미는 "본디의 것으로 다시 돌아오는 것"이다.

정의된 함수 func()가 있다고 할 때 해당 함수 내부에서 자기 자신 즉 func()를 호출하는 것이다.

 

재귀호출의 구조

def func(n):
    if n == 0:			# 재귀 호출을 탈출할 수 있는 조건을 명시해야 한다.
        return 1:
    else:
        return func(n-1))	# 함수 내부에서 동일 함수를 호출한다.

 

재귀호출 예제1 - factorial

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

print(factorial(5))	# 5*4*3*2*1 = 120

 

 

재귀호출 예제2 - 유클리드 호제법

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

print(gcd(162, 192)) # expected value is 6

 

재귀호출로 구현된 내용은 반복문으로 구현 가능하고 그 역도 성립한다.

 

재귀 호출을 사용하면 코드의 의미가 알기 쉬워지는 경우도 그렇지 않은 경우도 있다. 전자의 경우에 대해서만 적용하도록 한다.

 

재귀 호출 시 주의할 점은 재귀 호출 깊이에 제한이 있다는 점이다. 따라서 명확한 탈출 조건을 지정해야만 한다.

 

연쇄적인 재귀호출이 진행되는 가운데 특정 조건에 부합하여 재귀를 중단하고 그 결과를 사용해야 하는 경우 재귀호출 자체를 반환하도록 작성한다.

---

2. 꼬리재귀

python은 꼬리재귀 최적화를 지원하는 언어가 아니라 크게 효과는 없지만, 지원하는 언어에서 꼬리재귀 형식으로 알고리즘을 작성하면 선형 알고리즘으로 변환해줘서 system stack memory의 낭비를 막고 실행속도면에서도 이득을 볼 수 있는 스킬이기에 개념을 익혀보고자 한다.

 

꼬리재귀를 위해서는 재귀호출에 대한 반환 값에 어떤 연산도 가하지 않고 그대로 상위 레벨 호출에 대해 반환하도록 하는 구조로 작성하면 된다. 위에서 소개한 팩토리얼 알고리즘은 return n * factorial(n - 1)  과 같이 깊은 호출의 반환 값에 연산을 한 결과를 반환하도록 하고 있기 때문에 꼬리재귀가 아니다. 이를 꼬리재귀 형태로 수정하면 다음과 같다.

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

print(factorial(5))	# 5*4*3*2*1 = 120

꼬리 재귀를 위해 반환할 값을 연산하여 저장할 매개변수를 하나 더 선언하고 초기화 한다.

깊이를 더해가며 재귀호출을 진행할 때 매개변수 값을 업데이트 한다.

재귀 탈출 조건에 부합할 때 매개변수를 반환한다.