[알고리즘] 재귀함수-기본, 누적합

💡재귀함수란?

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 재귀함수는 재귀가 모두 실행되어 끝나거나, 특정 브레이크 포인트를 만날 때까지 계속해서 실행되는데, 만약 브레이크 포인트를 제대로 설정하지 않으면 무한루프의 늪에 빠질 수도 있다. 함수가 무한대로 실행되면 스택 오버 플로우 문제가 발생하게 된다.

재귀함수 구현 시 고려사항

1. branch와 level을 고려한다.

   branch는 하나의 재귀 함수에서 뻗어나가는 가지의 개수를 의미하고, level은 들어가고 싶은 마지막 깊이를 의미한다. return을 어느 단계에서 할지 같이 고민하면 좋다.

2. 매개 변수를 고려한다.

   sum, level, now등 어떤 변수를 매개변수로 가져갈지 고려해야 한다. 전역으로 뒀을 때 편한 것과 매개변수로 뒀을 때 편한 것을 구분하여 사용한다.

3. visited 배열의 사용 유무와 원상 복구를 고려한다.
   중복을 제거해야할 경우 visited 배열으로 방문 처리를 해줘야 한다. 그리고 재귀 함수 들어가기 전에 변경했던 값을 재귀가 끝나고 다시 돌아오는 경우에 원래의 상태로 되돌려 놔야 하는지 아닌지는 문제에 따라 다르므로 이를 고려하여 설계해야 한다.

# 재귀 함수로 리스트의 누적합 구하기
# 출력: 3 7 12 13 19 28

arr=[3,4,5,1,6,9]

# 1. 전역 변수 사용
sum = arr[0]
def abc(level):
    global sum
    if level == len(arr)-1: # 마지막 인덱스가 되면 sum 출력
        print(sum)
        return
    print(sum)
    sum+=arr[level+1]
    abc(level+1)
    
abc(0)

# 2. 지역 변수 사용
def abc(level,sum):
    if level == len(arr)-1: # 마지막 인덱스가 되면 sum 출력
        print(sum)
        return
    print(sum)
    abc(level+1,sum+arr[level+1])

abc(0,arr[0]) # level sum

# 거꾸로 누적합 구하기
# 출력: 28 19 13 12 7 3

# 전역
arr=[3,4,5,1,6,9]

def abc(level,sum):
    if level==len(arr)-1:
        print(sum)
        return
    abc(level+1,sum+arr[level+1])
    print(sum)

abc(0,arr[0])

# 지역
sum=arr[0]
def abc(level):
    global sum
    if level==len(arr)-1:
        print(sum)
        return
    sum+=arr[level+1]
    abc(level+1)
    sum-=arr[level+1]
    print(sum)

abc(0)

# 3개의 카드 묶음에서 1장씩 뽑았을때
# 나올 수 있는 모든 합들을 출력해 주세요

arr=[3,7,1,5] # 카드의 종류, 카드의 개수는 많음
# lv=3 (3장)
# br=4 (카드의 종류)

# 1. 전역
sum=0
def abc(level):
    global sum
    if level==3:
        print(sum, end=' ')
        return
    for i in range(4):
        sum+=arr[i]
        abc(level+1)
        sum-=arr[i] # 재귀 탈출하면 그 다음 가지를 위해 다시 빼줌

abc(0) # level

# 2. 매개

def abc(level,sum):
    if level==3:
        print(sum,end=' ')
        return
    for i in range(4):
        abc(level+1,sum+arr[i])

abc(0,0) # level sum

🎈 동전의 최소 개수

# 거스름돈 돌려둘 때 동전 개수의 최소
coin = [100,70,10] # 동전 종류

N = int(input()) # 거슬러야 할 돈
min_cnt = int(21e8)

def abc(N, cnt):
    global min_cnt
    if N < 0: # 가격이 안 맞으면 그냥 리턴
        return
    if N == 0: # 가격이 맞을 때 최소 갱신
        if min_cnt > cnt:
            min_cnt = cnt
        return
    for i in range(3):
        abc(N - coin[i], cnt+1)

abc(N, 0)

print(min_cnt)