[6주차] 재귀함수

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

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

 

<예시문제> data = [3, 5, 8]의 성분들의 합으로 표현할 수 있는 숫자의 경우의 수는? 

2^3이라고 생각할 수 있지만 중복된 값이 있음 (0, 3, 5, 8, 8, 11, 13, 16 → 중복된 값 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]*j + data[2]*k)
print(result)  ---> {0, 3, 5, 8, 11, 13, 16}

완전 탐색으로 구현할 경우 답은 잘 나오지만 만약 리스트에 담긴 데이터의 수가 많아진다면 반복문의 개수 너무 많아진다! (성분의 개수 = 반복문의 개수) → 재귀함수 사용해야 한다.

 

- 재귀함수 사용 이유 : 코드의 간결화 및 변수 사용 최소화

 

def recur(index, value):
	if index == len(data):                   # 재귀함수 종료 구문
    	result.add(value)
    else:                                        # 재귀함수 본문
    	recur(index+1, value + data[index])  
        recur(index+1, value)

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

 

<팩토리얼>

def factorial(n):
	if n == 1:
    	return 1
    else:
    	return n * factorial(n-1)
        
print(factorial(5))    ----------> 120

 

<피보나치 수열> : 두 수의 합이 다음 수가 되는 수열

1, 1, 2, 3, 5, 8, ...... 

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

 

- 재귀함수 깊이 : 파이썬의 defualt 최대 깊이는 1000