[자료구조] 재귀(Recursion) 정리

1. 재귀(Recursion) 이란?

자료구조에서 재귀(recursion)는 함수의 실행 과정에서 자기 자신을 호출하는 함수를 의미합니다.

 

Example : Factorial Function

재귀의 간단한 예시는 팩토리얼(Factorial) 함수를 예로 들 수 있습니다.

팩토리얼 함수를 수식으로 표현하면 다음과 같습니다.

$$ f(n) = \begin{cases} 1 & n = 0 \newline n \cdot f(n-1) & else \end{cases}   \quad where \ n \in \mathbb{Z}^+$$

위 수식을 Python으로 구현하면 다음과 같이 구현해 볼 수 있습니다.

 

Factorial 함수 구현(Python)

 

2. 재귀 함수 구현 시 주의사항

다음으로는 재귀함수를 작성할 때 반드시 포함되어야 하는 부분은 (1) Base case와 (2) Recursive call을 반드시 포함해야 합니다. 만약, 두 가지 조건을 모두 만족하지 못하는 경우, 함수가 정상적으로 작동하지 않습니다.

2.1. 기본 케이스(Base Case)를 반드시 만들어야 한다.

기본 케이스란, 재귀 호출(Recursive call)을 수행하지 않는 입력 변수의 반환값을 의미합니다. 재귀적으로 함수가 반복적으로 호출되었을 때, 제일 마지막 호출에서는 Base Case에 도달해야 합니다. 그렇지 않는다면 무한번 자기 자신을 호출하게 되므로 함수가 끝나지 않게 됩니다. 파이썬의 반복문 중 'While True : '와 비슷하다고 생각하시면 됩니다. 앞선 Factorial 예시에서는 4번째 줄이 Base case가 됩니다.

2.2. 반드시 Recursive Call이 있어야 한다.

재귀함수는 자기 자신을 호출해야 하므로, 반드시 함수 내에 자기 자신을 호출할 수 있도록 해 주어야 합니다. 앞선 예시에서는 7번째 줄이 이 부분에 해당한다고 볼 수 있습니다.

 

위 경우를 다시 정리해서 앞의 예시를 다시 살펴보면 다음과 같습니다.

 

Base case & Recursive call

 

3. 재귀함수의 작동 방식

앞의 예시를 다시 한번 살펴보겠습니다. 예를 들어 Factorial(4)를 실행시킨 경우를 살펴보겠습니다.

 

Factoria(4) 작동 과정

처음 우리가 factorial(4)를 호출하였다면, n에 해당하는 4는 0보다 크므로 else에 걸리게 됩니다. 그렇게 되면 factorial(4) 함수는 잠시 동작을 멈추고 factorial(3)을 호출하게 됩니다. 호출된 factorial(3)도 마찬가지로 0보다 크게 되므로 factorial(2)를 호출하게 됩니다.

이렇게 계속 작동하다가 factorial(1)이 factorial(0)을 호출하는 경우에, factorial(0)은 4번째 줄의 조건을 만족하므로 factorial(-1)을 호출하지 않고 바로 factorial(1)에게 1을 return 하게 되고, factorial(1)의 결과가 나오게 됩니다.. 마찬가지로 factorial(2)는 factorial(1)의 return을 받을 수 있게 되며, 최종적으로 우리가 원하는 factorial(4)의 결과를 받아볼 수 있게 됩니다.

 

4. 재귀함수의 장단점

[장점]

• 변수를 여러 개 만들 필요가 없다.
• while이나 for loop를 사용하지 않기 때문에 코드가 간결해진다.

[단점]

• 재귀 호출이 많이 발생할수록 메모리를 더 많이 사용하게 된다.
  (Example : factorial(1000000000000)을 실행하는 경우)

5. 꼬리 재귀(Tail Recursion)

마지막으로 Recursion의 한 종류인 꼬리 재귀(Tail Recursion)에 대해 정리해 보겠습니다.

꼬리 재귀(Tail Recursion)이란, 기존 재귀함수 구현 방식에서 콜 스택이 깊어지는 경우(재귀 함수 호출이 계속해서 쌓이는 경우), 스택오버플로우(Stack overflow)가 발생하는 것을 방지하기 위해 제시된 방법입니다. 일반 재귀함수와는 다르게, 꼬리 재귀는 재귀 함수 호출이 끝나면 아무 연산도 하지 않고 결과만 바로 Return 합니다. 똑같이 factorial을 예시로 들면 다음과 같은 방식입니다.

 

Tail Recursion : Facotorial function

 

5.1. Recursion VS Tail Recursion

factorial 함수로 살펴보겠습니다. 일반적인 재귀로 구현한 Factorial 함수는 제일 마지막 재귀가 끝나면 추가적인 연산(곱연산)을 한 뒤에 return 하지만, Tail recursion은 마지막 재귀가 끝나면 처음 호출한 함수의 결괏값 계산이 끝나기 때문에, 해당 결과만 이전에 호출한 함수에 return 합니다.

 

recursion VS tail recursion

 

6. 연습문제 : 백준 11050번 - 이항계수

재귀함수를 연습해 볼 수 있는 문제로 백준의 11050번 문제를 추천드립니다!
사이트 : https://www.acmicpc.net/problem/11050

백준 11050번

제가 작성한 예시 답안은 다음과 같습니다.(직접 풀어보시는 걸 추천드립니다!)

def recursive(n,k,acc):
    if min(n,k) == 0:
        return round(acc,1)
    return recursive(n-1,k-1,acc*(n/k))

n,k = map(int,input().split())
ans = int(recursive(n,k,1))
print(ans)