[파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

재귀(recursion)란?

 

 같은 알고리즘을 사용하여 정의한 알고리즘을 재귀 알고리즘이라고 합니다. 어떠한 역할을 하는 함수에 자기 자신을 다시 호출하여 재귀 알고리즘을 적용할 수 있고, 이러한 함수를 재귀 함수라고 합니다.

 

---

재귀 함수

 

재귀 함수를 배우기 전에 재귀 함수는 스택을 활용하기 때문에 우선 스택 자료구조에 대해 어느 정도 알아야 합니다. 

 

2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

 

일반적으로 함수를 호출하면 메모리에서 스택 영역에 해당 함수에 대한 정보가 리턴 주소(return address), 파라미터 값, 메모리 주소 등이 포함되어 저장이 되고, 함수 실행이 끝나면 해당 함수에 대한 정보가 pop 됩니다. 

def DFS(n):
    if n < 1:
        return
    print(n, end=' ')
    DFS(n-1)
    
DFS(5)
# 5 4 3 2 1 출력

 

위의 코드로 예를 들어보겠습니다. 첫 번째로 DFS(5)로 함수를 호출합니다.

그럼 스택엔 위와 같이 DFS(5) 함수 호출에 대한 정보가 쌓이게 됩니다.

DFS(5) 함수가 실행 되면서 5를 화면에 출력하고 다음 줄에 또 DFS(4)를 호출하여 스택엔 위와 같이 함수 정보가 저장이 됩니다.

DFS(1)까지 같은 재귀 호출이 되다가 DFS(0)에서는 n이 0이고, 0은 1보다 작으므로 재귀 호출을 하지 않고, return을 하여 바로 함수를 종료하게 됩니다. 바로 이런 조건을 베이스 케이스(Base case)라고 하며, 재귀 함수에서는 이 베이스 케이스가 아주 중요합니다. 

DFS(0) 함수는 그대로 종료가 되어 스택에서 제거되고, 저장하고 있던 리턴 주소로 돌아가게 됩니다. 이때 리턴 주소는 DFS(1) 함수에서 DFS(0) 함수를 호출한 다음 주소가 되겠습니다.

 

DFS(1)에서는 DFS(0) 함수 호출 다음에 바로 함수가 종료되므로 그대로 DFS(1) 함수도 종료되어 스택에서 제거됩니다.

 

나머지 함수 정보들도 같은 메커니즘으로 스택에서 차례대로 제거가 됩니다.

 

재귀 함수와 스택의 상관관계에 대해서 어느 정도 이해가 가시죠!?

 

---

재귀 함수의 장단점

 

재귀 함수는 점화식과 베이스 케이스만 구하면 된다는 점에서 가시성이 높고, 구현하기 쉽다는 장점이 있지만 메모리를 크게 차지한다는 단점이 있습니다. 또한 무한 재귀에 빠지게 되면 스택 오버플로우를 초래할 수 있는 치명적인 단점도 갖고 있습니다.

 

---

재귀 함수의 사용 예

 

유클리드 호제법

2022.07.01 - [알고리즘(파이썬)/코딩테스트] - [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3)

[프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3)

 

피보나치수열

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))
# 5 출력

 

이진수 출력

def binary(n):
    if n > 0:    
        binary(n//2)
        print(n%2, end='')
binary(11)
# 1011 출력