[자료구조] 재귀함수

재귀함수

0) 정의 

-> 메소드 혹은 함수의 내부에서 자기자신의 메소드 혹은 함수를 다시 호출하는 함수 

 

1) 구조 

def solution(trump, loc):
    if 종료조건: 
    	pass
    return solution(trump, loc + 1)

* 재귀함수 사용시에는 조건문을 활용하여 재귀함수 종료조건을 삽입해야 함 

 

2) 사용 이유

-> 코드의 간결화 및 변수 사용 최소화 

 

3) 재귀함수 깊이 

* 재귀함수의 최대 깊이 기본값은 1,000이지만, 다음과 같이 옵션을 설정해주면 최대 깊이 제한을 변경 할 수 있다. 

import sys 

sys.setrecursionlimit(2500)

4) 활용 예시

Q. data = [3, 5, 8] 성분들의 합으로 표현할 수 있는 숫자의 경우의 수는 ?

· 반복문을 활용한 완전 탐색 

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] * i + data[2] * k)

data의 개수가 늘어나면 늘어날수록 반복문의 개수 증가 -> 엄청난 시간복잡도 

 

· 재귀함수를 이용한 완전탐색

data = [3, 5, 8] 
result = set() 

def recur(index, value):
    if index == len(data):
        result.add(value)
    else: 
        recur(index + 1, value + data[index])
        recur(index + 1, value) 

recur(0, 0)

Q. 팩토리얼을 재귀함수로 작성하라 

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

Q. 피보나치 수열을 재귀함수로 작성하라 

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