Recursion(재귀)

본 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리하는 글입니다.

순환(재귀) 함수란?

 

함수가 자기자신을 호출하는 함수의 형태

 

def function(...){
    ...
    function(...);
    ...
}

 

순환 함수는 무한루프에 빠지는가?

 

재귀함수는 자기 자신을 호출하기 때문에 무한 루프에 빠지기 쉬운 구조를 가진다.

때문에 무한루프를 피하기 위해서는 아래와 같은 두 가지 조건을 만족해야한다.

 

1. Base case(종료 조건) : 적어도 하나는 recursion에 빠지지 않는 경우가 존재해야한다.

2. Recursive case : 모든 Case는 Recursion을 반복하다 Base Case로 수렴해야한다.

 

순환 함수와 수학적 귀납법

 

func(int n)은 음이 아닌 정수 n에서 0에서 n까지의 합을 계산하는 함수라면

 

1. n=0 : n=0을 반환 (올바르다)

2. 임의의 양의 정수 k에 대해서 n<k인 경우, 0에서 n까지의 합을 올바르게 계산하여 반환한다면,

3. n=k : func(k)는 func(k-1) + k이고 func(k-1)은 2에 의해 올바르므로 n=k일 때도 성립한다.

 

Iteration(반복문) vs Recursion(순환 함수)

 

모든 Recursion은 반복문으로 표현할 수 있다. ↔ 모든 반복문은 Recursion으로 표현할 수 있다.

 

순환함수는 반복문에 비해 복잡한 알고리즘을 단순하고 알기 쉽게 표현할 수 있지만,

함수 호출에 따른 오버헤드가 있다.

 

순환적 알고리즘의 설계

 

1. Base case(종료 조건) : 적어도 하나는 recursion에 빠지지 않는 경우가 존재해야한다.

2. Recursive case : 모든 Case는 Recursion을 반복하다 Base Case로 수렴해야한다.

3. 암시적(Implicit) 매개변수를 명시적(Explicit) 매개변수로 바꾼다.

 

하노이의 탑

 

L에 있는 탑을 R로 옮겨야한다.
이 때, 지름이 작은 원판 위에 지름이 큰 원판을 올릴 수 없다.

 

만약 n = 1이라면, L에 있는 원판을 R로 한 번만 옮기면 되므로 1번이다.

n < k인 n에 대해서 n개의 하노이의 탑을 옮기는 데 드는 횟수를 T(n)라 가정하면

만약 n= k라면, k-1개의 탑을 M으로 옮긴 후 가장 큰 원판을 R로 옮기고 다시 n-1개의 탑을 R로 옮기면 된다.

 

T(n)       #L에서 R로 n개를 옮기는데 걸리는 횟수
= T(n-1)   #L에서 n-1개를 M으로 옮기는데 걸리는 횟수
+ 1        #가장 큰 원판을 R로 옮기는데 걸리는 횟수
+ T(n-1)   #M에서 n-1개를 R로 옮기는데 걸리는 횟수

 

이를 바탕으로 재귀함수로 구현하기 위해 분석해보면,

 

Recursive Case : n개의 원판을 옮기는 것. 원판의 개수를 하나씩 줄여가면서 반복

Base Case : 옮기는 원판의 개수가 1개일 때, T(1) = 1

명시적 매개변수 : 원판의 개수 n

 

def solution(n):
  if n == 1:
    return 1
  else:
    return 2*solution(n-1) + 1  #solution(n-1) + 1 + solution(n-1)

 

미로찾기

input = [[0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1], [0, 1, 0, 0]]
output = True

 

(0, 0)에서 시작해서 도착지인 (3, 3)까지 도착하(기만 하)는 알고리즘을 짜볼 것이다.

아이디어는 다음과 같다.

 

 

1. 내가 있는 칸 중 동, 서, 남, 북의 칸에 대해서 도착지로 향하는 경로에 포함되는지 아닌지를 조사한다.
2. 내가 있는 칸이 도착지라면, 도착지로 향하는 경로에 포함된 것이다.

 

이를 바탕으로 재귀 함수를 구하기 위해 분석해보면,

 

• Recursive Case : 내가 있는 칸의 동, 서, 남, 북의 칸들이 도착지까지 가는 경로에 포함되는지 조사한다.
• Base Case : 조사한 칸이 출구일 때
• 명시적 매개변수 : 행렬의 row, col index

순환적 알고리즘 설계에서 Recursive Case를 짤 때, 모든 Case에 대해 Base Case로 수렴해야한다.

그런데 현재 Recursive Case에서 동서남북을 모두 조사하기 때문에 동쪽의 칸을 조사하고,

다시 동쪽의 칸에서 서쪽의 칸을 조사하면 무한루프에 걸린다는 것을 알 수 있다.

즉, Recursive Case가 무한 루프에 걸리는지 잘 조사해야한다.

이를 바탕으로 수정하면,

 

• Recursive Case : 내가 있는 칸의 동, 서, 남, 북의 칸들이 방문하지 않은 칸이면서 도착지까지 가는 경로에 포함되는지 조사한다.
• Base Case : 조사한 칸이 출구일 때
• 명시적 매개변수 : 행렬의 row, col index, 지도 행렬 map, 도착지점 target

이다.

또, index만으로 성분 값을 알 수 없기 때문에 지도 행렬을, 도착 지점인지 비교하기 위해 target을 매개변수로 넣어주었다.

 

함수를 만들기 위해 발생할 수 있는 Case에 대해서 자세히 분석해보면

방에 들어가서 동, 서, 남, 북을 조사할 경우, 다음과 같은 5가지 Case를 만난다.

 

1. 미로 밖 : index가 0보다 작아지거나 len(map)과 같거나 커지면 return False
2. 벽 : 벽이라면 성분 값이 1이고 return False
3. 출구 : 칸의 index가 (n, n)이라면 return True
4. 방문한 칸 : 성분 값이 2라면 방문한 칸이므로 return False
5. 방문하지 않은 칸 : 사방으로 재귀함수를 호출하여 return 받은 결과값을 조합하여 return한다.
    5-1. 출구 경로인 칸 : 출구 칸에서 return된 True를 return 받는다.
    5-2. 출구 경로가 아닌 칸 : 막힌 곳에서 return된 False를 return 받는다.

 

만약 출구 경로가 아닌 통로에서 오는 False와 출구 경로에서 오는 True를 둘 다 받는 칸이 있다면,

이 칸은 출구 경로에 포함되는 칸이므로 True가 되어야하고 이는 or 연산으로 False와 True를 연산하여 도출할 수 있다.

즉, 출구가 아닌 칸에 대해서는 사방의 칸들에 대한 return값의 or 연산을 통해 값을 return하므로써 5-1, 5-2번을 통합할 수 있다.

 

def solution(map, current, target):
  x = current[0]
  y = current[1]

  #1. 미로 밖
  if x < 0 or x >= len(map) or y < 0 or y >= len(map):
    return False

  if map[x][y] == 1 or map[x][y] == 2: #2. 벽 or 4. 방문한 칸
    return False
  elif current == target: #4. 출구
    map[x][y] = 2
    return True
  else: # 5. 방문하지 않은 칸
    map[x][y] = 2 #방문 체크
    return solution(map, (x+1, y), target) or solution(map, (x, y+1), target) or solution(map, (x-1, y), target) or solution(map, (x, y-1), target)

 

재귀 함수부를 조건문 안으로 넣어서 경로가 아닌 경우를 3으로 표시해줄 수도 있다.

 

def solution(map, current, target):
  x = current[0]
  y = current[1]

  #1. 미로 밖
  if x < 0 or x >= len(map) or y < 0 or y >= len(map):
    return False

  if map[x][y] == 1 or map[x][y] == 2: #2. 벽 or 4. 방문한 칸
    return False
  elif current == target: #3. 출구
    map[x][y] = 2
    return True
  else: # 4. 출구 경로가 아닌 칸 or #출구 경로인 칸
    map[x][y] = 2 # 방문 체크
    if solution(map, (x+1, y), target) or solution(map, (x, y+1), target) or solution(map, (x-1, y), target) or solution(map, (x, y-1), target):
      return True
    
    map[x][y] = 3 # 5-2. 출구 경로가 아닌 칸 표시
    return False

 

Counting Cells in a Blob

 

다음과 같이 배경(0)과 이미지(1)로 구성된 NxN 이미지가 있을 때,

하나의 좌표 (x, y)에 대해 이 점이 연결된 이미지의 집합(= blob) 안에 있다면, 이 집합에 있는 이미지(1)의 개수를 세는 알고리즘.

(대각선에 위치하는 것 역시 이어진 것으로 본다)

 

입력 : 
    1. N*N 크기의 2차원 그리드
    2. 하나의 좌표(x, y)

출력 :
    픽셀 (x, y)가 포함된 blob의 크기,
    미포함 시 0 반환

 

• Recursive Case : 현재 픽셀이 방문하지 않은 이미지 픽셀이라면 둘레 픽셀을 조사한다.
• Base Case : 현재 픽셀이 배경 픽셀이거나 방문했던 이미지 픽셀이라면 return 0
• 명시적 매개변수 : N*N 크기의 2차원 그리드, 현재 좌표 (x, y)

출력이 (x, y)가 포함된 blob의 크기이기 때문에 좌표를 입력 받으면 자신을 둘러싼 8개의 칸을 모두 둘러보고,

그 중 이미지 픽셀이 있다면 다시 함수를 호출해서 그 이미지 픽셀을 둘러싼 픽셀들을 살펴보려고 한다.

그러려면 무한 루프에 걸릴 수 있기 때문에 방문한 픽셀은 따로 표시해 주어야한다.

정확한 알고리즘과 return 값을 정하기 위해 모든 Case를 살펴보면

 

1. 맵 밖 : 맵 밖이므로 호출 불가, return 0
2. 배경 픽셀 : 성분 값이 0, blob에 포함되지 않기 떄문에 return 0
3. 방문한 픽셀 : 성분 값이 2, 이미 방문했기 때문에 return 0
4. 방문하지 않은 픽셀 : 성분 값이 1, 방문 체크하고 둘레 픽셀 호출
   4-1. 주위에 방문하지 않은 이미지 픽셀이 없는 이미지 픽셀 : 주위 픽셀에서 return 받은 값의 총합이 0, return 0 + 1
   4-2. 주위에 방문하지 않은 이미지 픽셀이 있는 이미지 픽셀 : 주위 픽셀에서 return 받은 값의 총합 + 1을 return

 

즉, 알고리즘은

 

1. 성분값 체크 후 배경, 맵 밖, 방문한 픽셀일 경우 return 0
2.  방문하지 않았으면 현재 픽셀 값을 2로 변경하고 주위 픽셀로  함수 호출
3. 반환받은 return 값들의 합 + 1(=자기자신)을 return

def solution(map, current):
  x = current[0]
  y = current[1]
  N = len(map)
  count = 0

  #맵 밖
  if x < 0 or x >= N or y < 0 or y >= N:
    return 0

  #배경 or 방문
  if map[x][y] == 0 or map[x][y] == 2:
    return 0

  #방문하지 않은 픽셀
  map[x][y] = 2 #방문 체크
  
  array_x = [x-1, x, x+1]
  array_y = [y-1, y, y+1]

  for p_x in array_x:
    for p_y in array_y:
      re = solution(map, (p_x, p_y))
      count += re

  return count + 1

 

N-Queesn Problem

 

체스에서 퀸은 상하좌우 + 대각선으로 움직일 수 있는 말이다.

NxN의 체스판에 N개의 퀸을 서로의 이동 경로가 겹치지 않도록 배치하라.

 

Backtracking

내가 결정을 내려가다가 막다른 골목에 닿으면 가장 최근에 내린 선택을 번복하며 진행하는 방법

 

상태공간트리

 

 

해를 포함하는 트리, 즉 이 트리를 전부 탐색하면 반드시 해가 나옴.

(모든 트리를 탐색해야하는 것은 아니다)

 

DFS (깊이 우선 탐색)

Backtracking + 상태공간트리

Recursion이나 Stack을 통해 구현할 수 있다.

 

Backtacking을 구현하는 Recursion 함수의 구조

 

// 1. function이라는 함수가 호출된 순간을 상태공간트리의 노드에 도착한 순간이라고 생각
return-type function(argiments){ // 2. 매개 변수는 내가 어떤 노드에 도착했는지 확인할 수 있는 정보가 주어져야한다.
  // 3. 노드에 도착하면 해야할 일들
  if non-promising // 3-1. 노드가 꽝인가?
    report failure or return;
  else if success // 3-2. 내가 찾는 노드인가?
    report answer and return;
  else // 3-3. 꽝도 아니고 답도 아닌가?
    visit children recursivley;
}

 

위의 구조를 따라 N-Queens Problem의 코드를 짜보자.

 

1. function이라는 함수가 호출된 순간을 상태공간트리의 노드에 도착한 순간이라고 생각

 

2. 매개변수는 내가 어떤 노드에 도착했는지 확인할 수 있는 정보가 주어져야한다.

 

코드의 복잡도를 줄이기 위해 전역변수 stack을 선언한 후 level 정보를 매개변수로 주고

level 내에서 어디 칸에 있는지(열 번호)는 stack에 넣어 저장한다.

예를 들어 2번째 줄 3번째 칸에 있다면 level = 2, stack에는 3이 들어간다.

return type은 간단하게 boolean으로 생각하자.

 

stack = [-1, 0, 0, 0, 0] #전역변수 0번째는 사용 안함.

def solution(level):
  if non-promising:
    report failure and return
  elif success:
    report answer and return
  else:
    visit children recursively

 

3-1. 이 노드가 꽝이라면,

 

현재 노드가 내가 찾는 노드가 아니라면 되돌아가기위해 return을 해주면 된다. 따라서 return False

찾는 노드인지 아닌지를 구분하는 함수 promising은 나중에 생각하도록 하자.

 

stack = [-1, 0, 0, 0, 0] #전역변수, 0번째는 사용 안함

def solution(level):
  if not promising(level):
    return False
  elif success:
    report answer and return
  else:
    visit children recursively

 

3-2. 이 노드가 정답이라면,

 

현재 노드가 내가 찾는 노드가 맞다면 return True를 해준다.

elif에 걸린다는 것은 마지막 level에서 promising 함수를 통과했다는 것과 같고

이는 NxN의 판에 모든 말이 놓였다는 의미과 같기 때문에 level == N이면 정답인 해를 찾은 것이다.

N을 전역변수로 따로 선언해준다.

 

stack = [-1, 0, 0, 0, 0] #전역변수, 0번째는 사용 안함
N = 4

def solution(level):
  if not promising(level):
    return False
  elif level == N:
    return True
  else:
    visit children recursively

 

3-3. 꽝도, 정답도 아니라면,

 

자식 노드를 recursivley하게 방문하도록 코드를 짠다.

else까지 도달했다는 것은 promising 함수를 통과했기 때문에

1번째 줄부터 level번째 줄까지는 이미 말이 놓였고, level + 1번째 말을 놓으러 가야하는 것이다.

level + 1 번째 라인에 말을 놓는 방법은 N개이기 때문에 for문을 len(stack)까지 돌려준다.

(∵체스판은 정사각형)

 

stack = [-1, 0, 0, 0, 0] #전역변수, 0번째는 사용 안함
N = 4

def solution(level):
  if not promising(level):
    return False
  elif level == N:
    return True
  else:
    for i in range(1, N+1):   #level+1번 말을 놓을 수 있는 위치 = N개
      stack[level+1] = i;
      if solution(level + 1): #만약 level + 1 이하의 라인들의 말들이 잘 놓아져서 True를 return한다면
        return True           #나도 True
        
    return False              #for문을 다 돌았는데 놓는 방법이 없다면 나도 틀린 것이므로 return Falsee

 

3-4. Promising 함수

 

매 순환마다 Promising 함수를 호출하므로 현재 level에 놓인 말 전의 말들은 전부 규칙을 만족

즉, 현재 놓인 말과 이전에 놓인 말들 간에 규칙만 테스트하면 됨.

level 순으로 배열하기 때문에 같은 행이 놓일 수는 없고,

 

1. 같은 열에 속하는지 : 숫자가 같은지

2. 대각선 방향에 속하는지 : 기울기의 절댓값이 1인지

 

테스트하면 된다. 따라서

 

def promising(level):
  for i in range(1, N):                                   #1~N-1까지
    if stack[i] == stack[level]:                          #같은 열에 속하는지
      return False
     
    if abs((stack[i] - stack[level]) / (i-level)) == 1:   #대각선에 속하는지
      return False
     
  return True

 

가 된다.

 

최종 코드

 

stack = [-1, 0, 0, 0, 0] #전역변수, 0번째는 사용 안함
N = 4

def promising(level):
  for i in range(1, level):
    if stack[i] == stack[level]:
      return False
     
    if abs((stack[i] - stack[level]) / (i-level)) == 1:
      return False
     
  return True

def solution(level):
  if not promising(level):
    return False
  elif level == N:
    return True
  else:
    for i in range(1, N+1):
      stack[level+1] = i;
      if solution(level + 1):
        return True
        
    return False
    
# 최초에는 solution(0)으로 호출한다.

내가 생각한 재귀 함수를 짜는 2개의 대표적인 형태

 

1. return 값으로 함수를 호출 : return 값을 조합하여 만드는 경우

2. 조건문의 조건에 함수를 호출 : return 값이 T/F인 경우, Backtracking을 사용하는 재귀 함수인 경우

 

재귀함수를 짤 때 먼저 시도해보면 좋을 듯.

 

내가 생각한 재귀함수의 분류 2가지

 

1. Backtracking을 사용하는 경우 : Base Case, Recursive Case를 명확히 분석

2. Backtracking을 사용하지 않는 경우 : 구조에 따라 차근히 구축