[자료구조💾] 3장 재귀호출

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

3.1 재귀호출의 개념

- 재귀호출(recursion) : 함수의 실행 중에 자기 자신을 다시 호출하는 상황

- 함수가 실행되면 함수의 실행 환경 정보(지역변수, 복귀주소 등)가 저장된 활성 레코드가 생성되어 시스템 스택에 추가된다. -> 재귀함수는 호출되는 횟수만큼 활성 레코드가 스택에 쌓임.

- 재귀 호출을 멈추는 조건인 종결 조건(exit condition)을 잘못 설정하면 무한 루프에 빠지게 된다.

 

 

3.2 이진 탐색

1) 이진탐색

- 순차 탐색(sequential search) 

• 원하는 원소를 찾을 때까지 순서대로 반복 비교를 수행한다.
• 정렬 과정 없이 바로 탐색을 수행할 수 있지만 탐색 성능 편차가 큰 편이다.

- 이진 탐색(binary search)

• 탐색 대상을 미리 정렬해야 한다.
• 정렬된 리스트의 중간 값(median)과 비교하여 탐색을 수행한다.
• 탐색 효율 : O(log₂n)
• 알고리즘
  1. 탐색 범위에 원소가 없으면 종료하고, 원소가 있으면 리스트의 중간 값(median)과 탐색 키(search key)를 비교한다.
  2. 탐색 키가 중간 값과 일치하면 그 위치를 반환하고 탐색을 종료한다.
  3. 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽 서브 리스트를 탐색범위로 변경하여 1번부터 수행한다.
  4. 탐색 키가 중간 값보다 크면 중간 값의 오른쪽 서브 리스트를 탐색범위로 변경하여 1번부터 수행한다.

 

2) 반복문으로 구현

def binary_search(lst, item, left, right):
    while left <= right:
    	mid = (left+right)//2
        if item == lst[mid]:
        	return mid
        elif item <lst[mid]:
        	right = mid-1
        else:
        	left = mid+1
    return -1

 

3) 재귀문으로 구현

def binary_search(lst, item, left, right):
    if left <= right:
    	mid = (left + right) // 2
        if item == lst[mid]:
        	return mid
        elif item < lst[mid]:
        	return binary_search(lst, item, left, mid-1)
        else:
        	return binary_search(lst, item, mid+1, right)
    return -1

 

 

3.3 피보나치 수열

- 정의 : 다음의 규칙을 따르는 수열

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2 (n ≥ 2)

- 구현

# 피보나치 수를 구할 때마다 이전 수를 구하기 위해 피보나치 함수 호출
def fibo1(n): 
    if n <= 1: 
    	return n
    else:
    	return fibo1(n-1) + fibo1(n-2)


# 이전에 구한 피보나치 수를 함께 반환하여 함수 중복 호출하지 않음, fibo1보다 효율적
def fibo2(n):
    if n <= 1: 
    	return (0, n)
    else:
    	(a, b) = fibo2(n-1)
        return (b, a+b)

 

 

 

3.4 하노이 타워

- 내용

• 3개의 기둥과 크기가 서로 다른 원반들이 존재할 때, 한 기둥에 꽂힌 원반들을 그 순서 그대로 다른 기둥으로 옮기는 문제
• 조건
  • 한 번에 하나의 원반만 옮길 수 있다.
  • 큰 원반이 작은 원반 위에 놓일 수 없다.
• 알고리즘 : 3개의 기둥 A, B, C가 있고 기둥 A에서 B로 n개의 원반을 옮긴다고 가정
  1. 기둥 A에서 n-1개의 원반을 A, B가 아닌기둥 C로 옮긴다. (재귀)
  2. 기둥 A에 남은 1개의 원반을 B로 옮긴다.
  3. 기둥 C에 있는 n-1개를 B로 옮긴다. (재귀)

- 구현

def htower(n, a, b):
    if n == 1:
    	print("Disc %d, moved from Pole (%d) to (%d)" %(n,a,b))
    else:
    	c = 6 - a - b # 비어 있는 기둥
        htower(n-1, a, c)
        print("Disc %d, moved from Pole (%d) to (%d)" %(n,a,b))
        htower(n-1, c, b)

 

3.5 미로 탈출

- 내용

• 전후 좌우 직선으로만 움직일수있는 로봇이 미로(2차원 배열)를 탈출하도록 함.
• 알고리즘
  1. 현재 위치(P)에서 주변 4방향(N, E, S, W)를 순서대로 검사하여 갈 수 있는 (벽이 아닌 미방문) 위치(P)를 찾는다
  2. 갈 수있는 위치(N)가 '탈출구(X)이면 '탈출 성공''으로 처리하고 종료한다.
  3. 갈 수있는 위치(N)가 '탈출구(X)'가 아니면 현재 위치(P)를 경로 리스트에 저장하고 새 위치(N)로 탐색 위치를변경하고 탐색 함수를 재귀 호출한다.
  4. 현재 위치(P) 주변에 갈 수 있는방향이 없으면 위치(P)를 경로 리스트에서 삭제하고 이전 위치로 되돌아가서 아직 탐색하지 않은 방향이 있으면 탐색을 재개한다.
  5. 더 이상 되돌아 갈 곳이 없고, 탐색할 방향이 없으면 '탈출 실패'로 처리하고 종료한다.

- 구현 (벽 : 1, 이동 가능 : 0)

found = False
path = []
mark = [[0]*10 for i in range(10)]
maze = [[...], [...], [...], [...], [...], [...], [...], [...], [...], [...]]


def rexplore(row, col):
    for x, y in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
        next_col = col + x
        next_row = row + y
        
        if maze[next_row][next_col] == 'X':
        	path.append((row, col))
            path.append((next_row, next_col))
            found = True
            return True
        elif maze[next_row][next_col] == '0' and mark[next_row][next_col]==0:
        	mark[next_row][next_col] = 1 # 방문 표시
            if (row, col) not in path:
            	path.append((row, col))
            result = rexplore(next_row, next_col)
            if result:
            	return True
            else:
            	path.pop()
    return False

 

3.6 N-QUEENS 문제

- 내용

• N개의 퀸이 서로 공격하지 않도록 N*N 체스판에 놓을 수 있는 위치를 찾는 문제
• 체스에서 퀸은 가로, 세로, 대각선 이동 가능
• 백트래킹 알고리즘 (backtracing algorithm)
  • 주어진 문제의 해(solution)를 구하기 위해 모든 가능한 경우를 나열해 하나씩 시도
  • 더 이상 하위 해에도달할 가능성이 없는  하위 경우는 제외해서 경우의 수를 줄이고 다음경우로되돌아가서 시도 하는 방법 

- 구현

class NQueens:
    def __init__(self, size):
    	self.size = size
        self.solution = 0
        self.col = [-1] * size
        
    def solve(self):
    	self.put_queen(0)
        print("Found", self.solutions, "solutions.")
  
    def put_queen(self, row):
    	if row == self.size:
            self.show_board()
            self.solutions += 1
        else:
            for col in range(self.size):
            	if self.check_pos(row, col):
                    self.col[row] = col
                    self.put_queen(row+1)

    def check_pos(self, rows, col):
    	for i in range(rows):
        	if self.col[i] == col or self.col[i]-i == col-rows or self.col[i]+i == col+rows:
            	return False
        return True
        
    def show_board(self):
    	for row in range(self.size):
        	line = ""
            for column in range(self.size):
            	if self.col[row] == column:
                	line += "Q "
                else :
                	line += "+ "
            print(line)
       	print("\n")