[알고리즘] 재귀함수의 정의와 조합과 순열 재귀함수로 구현하기 python

재귀함수 정의

컴퓨터가 수행하는 작업들은 대개 작은 조각들로 나누어 볼 수 있다. 그런데 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다. 완전히 같은 코드를 반복해 실행하는 for 같은 반복문이 좋은 예다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function)이다.

 

재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

 

조합과 순열 문제 간단한 반복문을 재귀함수로 변환하기

 

1. 조합

 

조합은 예를 들어 5개의 숫자를 4자리수 에 대한 숫자를 만들려고 할때 모든 경우를 구하는 것이다.

아래 문제를 보고 for문으로 먼저 코딩 해보자

 

문제1 : 0부터 차례대로 번호 매겨진 n개의 원소 중 4개를 고르는 모든 경우를 출력하라(5C4)

# ex) 0,1,2,3,4 => (0,1,2,3), (0,1,2,4) ... (1,2,3,4)

# 1. 반복문 이용
def solution(arr):
    n = len(arr)
    
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(k+1, n):
                    print(i,j,k,l)

solution([0,1,2,3,4])

for문으로 문제를 해결하려 하면 원소가 추가될 때마다 for문을 추가해야 하는 단점이 있다. 재귀로 코딩하면 소스를 수정할 필요가없어 확장성이 높다. 

 

위 문제를 재귀로 바꾸는 방법은 for문으로 원소 하나를 선택하고 다음 선택을 재귀로 선택하게 하면 된다. 그리고 원소 4개를 픽하면 return 하면 된다. 여기서 원소 4개를 픽하면 return을 하는 경우를 basecase라 한다.

 

f(n) = 1개선택 + f(n-1) ... => 4개 선택 하면 print하거나 먼 작업을 하고 return

 

# 2. 재귀 이용
def solution(arr):
    n = len(arr)
    picked = []
    start = 0
    def recur(start, n):
        # basecase
        if len(picked) == 2:
            print(picked)
            return

        # 1개선택
        for i in range(start, n):
            picked.append(i)
            # 재귀하면서 나머지 원소 선택
            start = picked[-1] + 1
            recur(start, n)
            picked.pop()

    recur(start, n)
    
solution([0,1,2,3,4])

 

 

2. 순열

 

순열은 조합과 다르게 순서를 고려하여 모든 경우의 수를 뽑는다. 조합에서는 (1,2,3), (2,1,3) 이 똑같지만 순열은 아니다.

위 조합 문제처럼 똑같이 반복문을 이용해 문제를 풀고 이를 재귀함수로 바꿔보자

 

문제2 : 0부터 차례대로 번호 매겨진 n개의 원소 중 2개를 순서로 고려해서 뽑는 모든 경우를 출력하라.(5P2)

# 2. 순열 반복문이용
def solution(arr):
    n = len(arr)

    for i in range(n):
        for j in range(n):
            if i != j:
                print(i,j)

solution([0,1,2,3,4])

 

# 2. 순열 재귀이용
def solution(arr):
    n = len(arr)
    picked = []

    def recur():
	# basecase
	if len(picked) == 4:
            print(picked)
            return

        for i in range(n):
            if i not in picked:
                # 1 pick
                picked.append(i)
                #재귀
                recur()
                picked.pop()

    recur()

solution([0,1,2,3,4])