[이코테_코딩테스트] 재귀 함수 (Recursive Function)

재귀 함수(Recursive Function)

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

def recursive_function():
	print("재귀 함수 호출")
	recursive_function()

recursive_function()

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다!

• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출

def recursive_function(i):
	# 100번째 호출 했을 때 종료
	if i == 100:
		return
	print(i, "번째 재귀함수에서", i + 1, "번째 재귀함수를 호출")
	recursive_function(i + 1)
	print(i, "번째 재귀함수를 종료합니다.")

recursive_function(1)

팩토리얼 구현 예제 (Python)

• 0! = 1! = 1

# 반복적으로 구현한 n!
def factorial_iterative(n):        
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
       result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):        
    if n <= 1: # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n - 1)

# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

최대공약수 계산 (유클리드 호제법) 예제 (Python)

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

• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있다.
• ex) GCD(192, 162)

Step	A	B
Step 1	192	162
Step 2	162 (Step 1의 B 값)	30 (Step 1의 A를 B로 나눈 나머지 R 값)
Step 3	30	12
Step 4	12	6

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

재귀 함수 사용의 유의 사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능
• 하지만, 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 함

• 모든 재귀 함수는 반복문을 이용하여 동일한 기능 구현 가능!

• 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음 → 더 좋은 방법을 고려해야 함

• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
• 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
• ex) DFS

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 3. DFS & BFS” 영상을 보고 작성하였습니다.