[python] 재귀함수(recursive function)

python의 꽃. DFS의 필수 개념인 재귀 함수에 대해 알아보자. 왜 재귀 함수를 알아야 할까? 미로 찾기 문제를 생각해보자. 미로를 찾기 하기 위해서는 매 순간 갈림길에서 선택을 해야 하는 순간이 생긴다. 갈림길에서 한 선택의 결과가 막힌 길이라면, 그 즉시 갈림길이 있었던 위치로 순간 이동하는 것을 가능하게 해주는 것이 재귀 함수다. 

 

0. 기본 모양

재귀 함수란 호출한 함수 안에서 그 함수를 다시 호출(recursive call)함으로 반복하는 것을 의미한다. 쉽게 말하면 def를 통해 함수를 만든다. 그리고 만든 함수 안에서 다시 그 함수를 호출하는 것을 의미한다. 아래의 예를 참고하자.

 

def recursive_call(x):
    print(x)
    recursive_call(x+1)
    
recursive_call(1)

 

위와 같은 방식으로 재귀 함수가 만들어진다. 물론 위와 같이 만들면, 무한 루프에 빠지게 된다. 자세한 이해는 아래에서 조금씩 알아가 보자.

 

 

 

재귀 함수는 무한루프에 빠지지 않게 하기 위해서 일종의 재동 장치가 필요하다. 그러한 이유로 함수의 인자에 호출 단계 k과 최종 단계 n를 포함한다. 다시 말하면 k로 원하는 목표까지의 카운트를 세고, 목표를 n이라고 표시하여, k == n인 경우에 함수 호출을 break 한다. 이해가 잘 안 될 수 있다. 간단한 아래의 기초 예제들을 보면서 이해를 해보자.

 

 

1. 기본형

호출 단계 k과 최종 단계 n를 포함한 2개의 인자로 만드는 것이다. 호출이 일어나는 순서울 살펴보자.

 

def function(k,n):
    if n == k:
        return
    else:
        function(k+1, n)

function(0,2)

 

function(0,2)를 호출하면 (메모리 영역이 구분되고 변수가 만들어진다.)

=> function(1, 2)를 호출하고 (메모리 영역이 구분되고 변수가 만들어진다.)

=> function(2, 2)가 되면 리턴한다. (메모리 영역이 구분되고 변수가 만들어진다.)

=> function(1, 2)로 돌아가서 없어진다.

=> function(0, 2)로 돌아가서 없어진다.

 

 

1.1. 배열의 각 원소를 재귀 함수로 접근하기

1,2,3 이 저장되어 있는 배열 A가 있다. A = [1, 2, 3]라는 배열에서 n인덱스를 선택하는 코드를 재귀로 작성해 보자.

k : 현재 호출에서 접근할 원소의 인덱스

n : 배열의 크기

 

def f(n, k):
    if n == k:
        print(A[k])
    else:
        f(n, k+1)

# 0부터 탐색하여 인덱스 2의 원소 print하기
f(2, 0)

'''
3
'''

 

위밍 업했으니 본격적으로 풀어봅시다.

 

 

 

1.2. 재귀로 집합 A의 부분집합 만들기

> 윤도, 재현, 소연이가 음식점을 갈 수도 있고, 안 갈 수도 있다. 하지만, 아무도 안 가지는 않는다. 이러한 경우의 수를 구하시오. ( 이렇게만 문제가 출제되진 않고, 다음 단계에 일어날 경우의 수도 추가시켜 문제가 출제된다.(고난도) )

 

• A = [1, 2, 3]
• b = i번 원소의 포함 여부를 나타내는 b

(point) 재귀 함수로 들어가기 전에 현재의 상태를 업데이트해줄 b 배열을 만들어 준다. 그래서 부분집합에 포함이 됐으면 1, 안 됐으면 0을 넣는 과정을 진행한다.

 

def f(k, n):
    if n==k: # b배열을 벗어나면
        for i in range(n):
            if b[i] == 1:
                print(A[i], end='')
        print()
    else:
        b[k]=0
        f(k+1, n)
        b[k]=1
        f(k+1, n)

A = [1, 2, 3]
b = [0, 0, 0]
f(0, 3)

'''
3
2
23
1
13
12
123
'''

 

 

 

 

1.3. 부분집합 원소의 합

> A의 부분집합 중 원소들의 합이 최대인 수를 print 하시오

 

• s : k-1번 원소까지 고려한 합
• 재귀 호출 시  f(k+1, n, s+A [k]), f(k+1, n, s)의 차이 : k번 원소까지 고려한 합에서  'k번을 포함할 경우는 s+A [k]'이고 'k번을 포함하지 않는 경우는 s'이다.

여기서의 코드의 특징은 우리는 부분집합의 형태를 보는 게 하니고 합만 찾고 있기 때문에, 위의 예시처럼 굳이 b배열을 만들지 않았다. 

 

# 부분집합 배열 합의 최대값 구하기.
def f(k, n, s):
    global maxV
    if n==k:
        if maxV < s:
            maxV = s
    else:
        f(k+1, n, s+A[k])
        f(k+1, n, s)
maxV = 0
f(0, 4, 0)
A = [1, 4, 3, 2]

print(maxV)
'''
10
'''

 

 

 

 

1.4. 서로 다른 n개의 자연수의 집합에서 부분집합 원소의 합이 M인 경우가 몇 번인지 구하기

• k : 0부터 카운터를 위한 변수
• n : A 집합의 개수
• s : 부분집합의 합
• M : 타깃 값( 부분집합의 원소의 합으로 임의 값 )

 

def f(k, n, s, M):
    global cnt
    if s==M:
        cnt+=1
        return
    elif n==k:
        return
    else:
        f(k+1, n, s+A[k], M)
        f(k+1, n, s, M)

A = [1, 2, 3, 4, 5, 6, 7, 8 ,9, 10]
cnt = 0
f(0, 10, 0, 42)
print(cnt)
'''
15
'''

 

 

 

여기까지 이해가 됐다면, 심화 단계로 넘어가기 전, 재귀에 대한 기초를 배운 것이다.