[Algorithm01] 재귀함수

재귀함수란?

함수 내에서 자기 자신을 호출하는 함수

하나의 함수가 실행되는 동안 다른 함수를 호출할 수 있으며 실행되는 동안 함수 자신조차 다시 호출할 수 있다.

def recur(n):
    if n==0:
        return print("끝났습니다")
    else:
        print(n)
        recur(n-1)

다음은 간단한 재귀함수의 예 이다.

다음의 함수는 n이 0일 때 print("끝났습니다")함수를 return 시키며 종료한다.
n이 0이 아닐때는 n을 출력하며 자기자신의 함수를 호출 시킨다.

이러한 재귀함수는 종료조건(기저조건)을 만나기 전까지 n을 출력시키고 자기 자신 recur(n-1)을 호출한다.

출력 결과는 다음과 같다.

5
4
3
2
1
끝났습니다

 

재귀함수는 사실 반복문을 깔끔하게 함축시켜놓은것과 같다.( 코드의 가독성과 유지보수성을 높임)

모든 재귀함수는 반복문으로 변경이 가능하다. 하지만 반복문은 중첩이 많아지면 많아질수록 코드의 길이가 길어지는 단점이있다.

즉, 재귀함수로 표현하면 가장 큰 장점이 중첩되는 반복문이 많아질 때 사용하면 유용하다는것이다. 반복 횟수가 미리 알려진 경우 재귀함수로 표현하는것이 중첩반복문을 사용하는것보다 깔끔하다.

다음장에서 순열과 조합에 대해서 이야기할텐데 그전에 중첩반복문을 어떨 때 재귀로 표현하는것이 유리한지 예를 들어보겠다.

 

1~n개의 카드 중에서 k개를 뽑는 조합(중복없이)

def combinations(n, k):
    combinations = []
    for i in range(n):
        for j in range(i + 1, n):
            for l in range(j + 1, n):
                for m in range(l + 1, n):
                    combinations.append([i, j, l, m])
    return combinations

n = 5  # 예시로 5개 중에서
k = 4  # 4개를 뽑는 경우의 수를 구합니다.
print(combinations(n, k))

k가 최대 4까지였을 때를 반복문으로 나타낸것이다.

k의 최대값이 늘어날수록 반복문의 중첩 수는 늘어날 것이다. 

(k의 값이 미리 주어지지 않은 경우 사실 반복문이 얼마나 늘어나야 할지 모르므로 구현이 불가능하다)

이것을 재귀함수로 표현하면

combis=[] # 만든 모든 조합을 담는 리스트
combi=[0]*n # k개를 뽑아 만든 조합
def combinations(start, depth):
    if depth == k: 
        combis.append(combi)
        return combis
    for i in range(start, n):
        combi[depth]=i
        combinations(i + 1, depth + 1)
        combi[depth]=0

n = 5
k = 4
print(combinations(0, 0))

 

이런식으로 표현할 수 있다. 

위의 재귀적 표현에 대해서 설명하자면 if depth==k는 기저조건이다.(재귀함수의 종료조건) 즉, 중첩 반복문의 횟수가 k가 되었을 때 그만 돌라는 의미이다.

종료조건을 만나지 않았다면 for문을 돌면서 n개중에서 첫번째로 한개를 선택한다.

그렇게 뽑은 한개를 combis라는 리스트에 담는다.

여기서 combi[depth]의 의미는 depth번째 뽑은 카드를 의미한다. 즉 depth번 뽑으면(반복횟수) combi에는 하나의 조합이 들어가는것이다. 그렇게 돌면서 모든 조합을 종료조건(k가 depth와 같아질 때)을 만날때 마다 combis에 만들어진 조합 combi를 담아준다. 최종적으로는 combis에는 모든 combi가 담기게 된다.

 

조합과 관련한 자세한 이야기는 다음의 순열과 조합편에서 다루겠다. 이번편에서는 반복문은 어떻게 재귀로 나타낼 수 있을까를 직접 고민해보고 어떠한 문제에서 재귀로 나타낼 수 있을지를 확인했다. 재귀의 핵심은 기저조건 종료조건을 잘 설정하는게 포인트다.

코드를 따라가면서 그려보면 combi[depth]=0을 왜해주는지에 대한 의문이 생길텐데 다음장을 보기전에 스스로 생각해보면 깨달음을 얻을 수 있다. (힌트: 재귀호출시 종료조건 후 돌아갈때를 생각해보자)