📚 재귀함수

📌 재귀함수란?

재귀함수란, 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다.
다른 말로는 재귀호출, 되부름이라고 부리기도 하며, 재귀 함수를 작성할 떄는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 합니다.

📌 예시문제

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

print(result)
# (0, 3, 5, 8, 11, 13, 16)

# 데이터가 많아지면 어렵기에 재귀함수를 사용함
data = [3, 5, 8]
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, 8, 11, 13, 16)
#배열의 길이가 길어진다 하더라도 수정없이 문제해결 가능

📌 재귀함수 활용

1. 펙토리얼(!)

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

2. 피보나치 수열

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

   📌 재귀함수 깊이