1️⃣ 재귀(Recursion)란?

위키백과 에서는 컴퓨터 과학에서의 재귀를 아래와 같이 정의한다.

컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다.

재귀 함수(Recursion)는 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
특정 분기 전까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

def factorial(n):
	if n == 1: # base case
    	return 1
    return n*factorial(n-1) # recursive case

2️⃣ 재귀 함수를 구상하는 방법

1. 함수의 정의
2. base condition
3. 재귀 식

3️⃣ Stack overflow

재귀 함수에서는 재귀 호출을 종료해주는 종료 조건(base case)이 중요하다.

def factorial(n):
    return n*factorial(n-1) # 반복적으로 실행되는 부분

이렇게 if문이 빠지게 되면, 함수는 멈추지 않고 -1, -2, ..., -n까지 무한하게 실행하게 된다.

파이썬에서는 최대 재귀 깊이(maximum recursion depth)가 1,000으로 정해져 있어, 최대 재귀 깊이를 초과하면 RecursionError가 발생한다.

import sys
sys.setrecursionlimit(100000) # 최대 재귀 깊이 변경

print(sys.getrecursionlimit()) # 설정된 최대 재귀 깊이 확인

자바나 C++에서도 메모리의 한계를 초과하면 StackOverflowError가 발생한다.

4️⃣ 재귀함수의 장단점

장점

1. 변수를 여러 개 만들 필요가 없다.
2. 코드가 간결해진다.

단점

1. 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 스택에 저장해야 한다. 이런 과정은 반복문에 비해 메모리를 더 많이 사용하게 된다.
2. 재귀 호출 후 복귀를 위한 과정에서 context switching 비용이 발생하여, 상대적으로 속도가 느리다.

5️⃣ 재귀함수의 단점 해결 방법

재귀 함수의 단점을 해결하기 위해 꼬리 재귀(tail call recursion)이라는 기법이 있다.
이는 컴파일러가 꼬리 재귀 코드를 보고, 적절한 반복문으로 컴파일을 해주어 동작하는 방법이다.

# Basic recursion
def factorial(n):
	if n == 1:
    	return 1
    return n*factorial(n-1)
    
# Tail call recursion
def factorial(n, total):
	if n == 1:
    	return 1
    return factorial(n-1, n*total)

꼬리 재귀에서는 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록하여 함수의 상태 유지 및 추가 연산을 하지 않아 스택 오버 플로우 문제를 해결할 수 있다.

위 코드에서 차이점을 보면 반환 부에서 연산이 없어진 것을 볼 수 있다.

6️⃣ 재귀함수를 활용한 알고리즘

• 병합 정렬, 퀵 정렬
• 이진 탐색
• 트리 탐색
• 그래프 탐색, BFS & DFS
• 동적 계획법
• 분할 정복
• 백트래킹