[알고리즘] 재귀

재귀 함수

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 이떄 이루어지는 호출을 재귀호출이라고 한다.

재귀 함수 단순 예제

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

위 예제는 어느 정도 출력하다 최대 재귀 깊이 초과 오류가 발생하는데, 이는 python에서 메모리 제한을 두었기 때문이다.
(RecursionError: maximum recursion depth exceeded while)

재귀 함수의 장단점

장점

• 직관적이며 간단하게 구현할 수 있다.

단점

• 재귀함수의 종료 조건을 잘 설정햊지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다.
• 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다.
• 불필요한 반복 연산을 하게 될 가능성이 있다.

재귀함수의 특징

1. 스택처럼 호출한 함수를 쌓았다가 종료조건을 만나면 위에서부터 하나씩 꺼래 처리하는 방식이다.
   

2. 종료 조건을 명시하지 않으면 함수가 무한히 호출되기 때문에 재귀 함수를 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

# 재귀 함수 일반적인 형태1
def function(입력값):
    if 입력값 > 제한값:
        return function(입력값-1)
    else:
        return 제한값 또는 특정값 # 👈 재귀 호출 종료

# 재귀 함수 일반적인 형태2
def function(입력값):
    if 입력값 <= 제한값:
        return 제한값 또는 특정값 # 👈 재귀 호출 종료
    function(입력값 보다 작은 값)
    return 결과값

재귀 호출과 반복문 비교

• 재귀 호출은 점화식과 종료조건만 구현하면 만들 수 있기 때문에 가시성이 높고, 구현하기 쉽다는 장점이 있다.
• 또한 재귀호출과 반복문 구현은 시간 복잡도는 같으나, 실제 Call Stack에 과정에서 재귀호출이 속도가 느리고, 메모리를 크게 차지한다.
• 즉, 반복문 구현은 전체 과정을 서술해야하기 때문에 재귀호출 보다 구현이 복잡하나 속도가 빠르고 호출의 제한이 없다는 장점이 있다.

재귀 함수 예제

팩토리얼을 구하는 함수를 만들기 위해서 재귀함수를 사용할 수 있다.
5!를 재귀적으로 생각해본다면 아래와 같은 과정을 거친다.

이것을 재귀 방정식으로 나타낸다면 다음과 같다.

여기서 1!은 더이상 재귀 호출을 해주지 않아도 되기 때문에 이 조건에서 재귀 호출을 종료해주면 된다.

이것을 시각적으로 표현한다면 아래와 같이 나타낼 수 있다.