[파이썬 알고리즘] 재귀 함수

재귀 함수의 기본적인 작동 원리

예시) 피보나치수열

# n번째 피보나치 수를 리턴
def fib(n):
    if n > 2:
        n = fib(n - 1) + fib(n - 2)
        return n
    else:
        return 1
 
 
# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

fib함수는 최소 계산 범위인 3번째 항을 제외하면 1을 리턴한다는 것을 먼저 생각했다. 그래서 따로 빼놨고 그다음 번째부터는 前 fib이 리턴하는 값과 前前 fib이 리턴하는 값을 리턴하도록 했다. 지금 생각해보니

return fib(n - 1) + fib(n - 2)을 해도 될 것 같다.

 

예시)  숫자의 합

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    if n == 1:
        return 1
    else:
        return triangle_number(n - 1) + n
 
 
# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

이 코드를 작성하기까지 아직 미숙한 터라 머릿속으로만 구상하기가 좀처럼 쉽지 않았다. 그래서 이렇게

손 구상도

종이에 적어서 구상해보도록 했다.

6 입력 시 앞의 5+4+...+1을 계산이 필요하고 5 입력 시 4+3+2+1이 필요하고를 반복하면 결국에는 계속 자기 자신의 함수를 불러와야 하는 규칙을 발견했다. 그래서 이것을 코드로 표현해보면 위처럼 나오게 된다.

 

예시) 리스트를 거꾸로 뒤집는 함수

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    n = len(some_list)
    if n == 1:
        return some_list
    else:
        return some_list[-1:] + flip(some_list[:-1])
 
# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

 

 

중요 예시) 하노이탑

 

하노이탑은 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것이다. 

한 번에 하나의 원판만 옮길 수 있으며 큰 원판이 작은 원판 위에 있어서는 안된다.

 

hanoi함수는 인스턴스로 num_disk(원판의 개수), start_peg(시작 위치 왼쪽 정렬), end_peg(끝 위치)를 받고

move_disk도 같은 인스턴스를 받아 기둥을 옮기는 문구를 출력한다.

 

이 하노이탑을 옮기기 위해서 생각해야 할 것은 기본 적인 성질이다. 지금 재귀함수를 공부하고 있으므로 연결지어 생각해보면 하노이 원판이 1개, 2개, 3개 늘어날 때 마다 2개일때는 1개일 때의 성질을 쓰고 3개일 때는 2개일 때의 성질을 갖다 쓰게 된다는 것을 알게되었다.

손고리즘

만약 원판이 3개일 때는 2개일 때 1번째에서 2번째로 옮기는 hanoi함수를 쓴다.

2개일 때 1번째에서 2번째로 옮기는 hanoi함수는 또한 1개일때 1번째에서 2번째로 옮기는 함수를 쓰며 이렇게 부르고 부르다 보면 어느샌가 0번째(존재하지 않는 원판)까지 도달하게 된다.

이 존재하지 않는 원판은 미리 if문으로 리턴하는 것이 없도록 하고 1개째에서는 원판을 옮기는 문구인 move_disk를 출력하도록 만들면 원판이 몇개던 n - 1, n - 2, ... , 1개째의 하노이 함수를 연속적으로 불러오면서 원판이 옮겨질 것이다. 

 

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))
 
def hanoi(num_disks, start_peg, end_peg):
    if num_disks == 0:
        return
    elif num_disks == 1:
        return move_disk(num_disks, start_peg, end_peg)
 
    mid_peg = (6 - start_peg - end_peg)
 
    hanoi(num_disks - 1, start_peg, mid_peg)
    move_disk(num_disks, start_peg, end_peg)
    hanoi(num_disks - 1, mid_peg, end_peg)
 
 
# 테스트 코드 (포함하여 제출해주세요)
 
hanoi(3, 1, 3)
 
 

재귀함수로 이렇게 코딩을하면 hanoi(4,1,3) 입력시

 

하노이 탑을 옮기는 법이 잘 출력된다.