[알고리즘] 재귀함수(Recursive Function)

빨려 들어간다 🌀🌀🌀

 

이 글은 동빈나 님의 이코테 강의를 정리한 글입니다.

 

 

 

1. 개요

✨ 정의

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

• 단순한 형태의 예제
  • '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력합니다.
  • 어느 정도 출력하다가 최대 재귀 깊이 초과(Maximum recustion depth exceeded) 메시지가 출력됩니다.

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! = 1 \times 2 \times 3 \times \cdots \times (n-1) \times n$

• 수학적으로 0!과 1!의 값은 1입니다.

 

# 반복적으로 구현한 n!
def factorial_iteration(n):
	result = 1
    for i in range(1, n+1):
    	result *= i
    return result

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

 

 

 

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

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

 

 

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

 

 

✨ 유의 사항

• 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있습니다. 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 합니다.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있습니다. 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있습니다.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓입니다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많습니다.