재귀함수

이번 포스팅은 자료구조의 재귀함수를 정리해보겠습니다.

재귀함수

재귀함수란?

메소드 혹은 함수의 내부에서 자기자신의 메소드 혹은 함수를 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다. 재귀 함수를 작성할 떄는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 합니다.

재귀함수 예시

data = [3, 5, 8] 일때 성분들의 합으로 표현할 수 있는 경우의 가지 수는?

아래의 코드에서 리스트 각각의 수에 대하여 얻을 수 있는 경우의 수는 두가지로 사용할때 사용하지 않을때 입니다. 그 숫자를 사용할때는 1을 곱해주고 사용하지 않을때는 0을 곱해주어 2번의 반복문을 통해 경우의 수를 낼 수 있습니다.

data = [3,5,8]
result = set()
for i in range(2):
    for j in range(2):
        for k in range(2):
            result.add(data[0]*i + data[1]*j + data[2]*k)
print(result)

{0, 3, 5, 8, 11, 13, 16}

위에 서는 리스트에 3개의 데이터만 있었기에 3번의 반복문으로 결과를 도출해 낼 수 있었지만 만일 data = [3, 5, 7, 10, 12, 15, 20]과 같이 7개의 데이터가 리스트에 있을때는 경우의 수를 도출해 내기 위해서 7번의 반복문이 필요해져서 구현이 어려워 집니다.

이때 재귀 함수를 사용하여 문제를 해결 할 수 있습니다. 즉 코드의 간결화 및 변수 사용 최소화가 재귀함수 사용의 목적입니다. 코드로 구현 하면 아래와 같습니다.

data = [3, 5, 7, 10, 12, 15, 20]
def recur(index, value):
    if index == len(data): # 재귀함수 종료 구문
        result.add(value)
    else:                  # 재귀함수 본문
        recur(index+1, value + data[index])
        recur(index+1, value)
        
result = set()
recur(0, 0)
print(result)

{0, 3, 5, 7, 8, 10, 12, 13, 15, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 29, 30, 32, 33, 34, 35, 37, 38, 39, 40, 42, 43, 44, 45, 47, 48, 49, 50, 52, 53, 54, 55, 57, 59, 60, 62, 64, 65, 67, 69, 72}

재귀함수 활용

재귀함수를 활용하는 대표적인 예는 팩토리얼 입니다. 팩토리얼을 재귀함수로 구현하면 아래와 같습니다.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(3))

6

두번째는 피보나치 수열이 있습니다. n=0, n=1 일때 첫번째 항의 값은 각각 1을 가지고 있습니다. 그 다음 항 n=2은 n=0과 n=1의 합 2를 가지고 있으며 n=3은 n=1과 n=2의 합 3이 되어 이러한 과정이 반복 됩니다.

def fibo(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
print(factorial(5))

120

재귀함수 깊이

파이썬이 재귀함수는 호출 1000번째 까지 가능하며 그 이상 호출 시 에러를 발생 합니다.

이때 sys.setrecursionlimit()를 이용하여 그 최대 깊이를 확장할 수 있습니다.

import sys
limit_number = 15000
sys.setrecursionlimit(limit_number)