재귀함수

재귀 함수

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

단순한 형태의 재귀 함수 예제

• '재귀 함수를 호출합니다'라는 문자열을 무한히 출력합니다.
• 어느 정도 출력하다가 최대 재귀 깊이 초가 메시지가 출력됩니다.

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)

 

팩토리얼 구현 예제

반복적으로 구현한 팩토리얼

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

print('반복적으로 구현:', factorial_iterative(5))

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

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

print('재귀적으로 구현:', factorial_recursive(5))

 

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

두 개의 자연수에 대한 최대공략수를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다.

유클리드 호제법

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

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

 

유의 사항

재귀함수를 잘 활용하면 복잡한 알고리즘을 간결히 작성할 수 있다.

• 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있다.

모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

반복문이 더 유리한 경우도 있다.

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

• 스택 라이브러리 대신 재귀함수를 이용하는 경우가 있다.

 

Reference

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법