Recursion 재귀

많은 일들은 대개 작은 조각들로 나누어 볼 수 있습니다. 그리고 한 조각이 작으면 작을수록 일은 단순해지고 반복되는 형태를 띄는 경우가 많습니다. 완전히 같은 코드를 반복적으로 하는 작업이 있다면 이때 재귀 함수(recursion fnction), recursion(재귀 호출)이 유용하게 사용될 수 있습니다.

1~100까지의 합을 구하는 경우를 재귀적으로 생각해봅시다.

1~100까지의 합은 100 + 1~99까지의 합으로 나눠서 생각할 수 있습니다.
마찬가지로 1~99까지의 합은 99 + 1~98까지의 합으로 볼 수 있겠죠.
"n + 1~n-1까지의 합" 이라는 과정은 완벽하게 동일합니다.
이를 코드로 구현해보면,

func sum(_ n: Int) -> Int {
  if n == 1 { return 1 }
  return n + sum(n-1)
}

n이 아무리 커지더라도 몇 줄의 코드로 간단하게 해결할 수 있습니다. n이 커지면 커질수록 재귀함수는 더욱 효율적이겠죠. 이때 주목할 건 첫 줄의 if문입니다. n이 1일 때 1을 리턴해주지 않으면 이 반복문은 끝나지 않습니다. 이처럼 재귀 함수가 가장 작은 단계까지 가서 더 이상 쪼개지지 않고 종료되는 재귀 호출을 기저 사례(base case)라고 합니다. 

기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 해야합니다.
(가장 작은 조각을 선택해야 됩니다.)
위 경우에서 n이 1인 경우가 아니라 n이 2인지 확인해서 3을 리턴하면 2보다 큰 경우는 잘 동작하겠지만 2보다 작아지는 경우는 문제가 생깁니다.

모든 반복문은 재귀 함수로 만들 수 있습니다. 당연히 그 역도 성립하지요. 0부터 번호가 매겨진 n개의 원소 중 4개를 고르는 모든 경우의 수를 출력하는 코드를 작성하려면 어떻게 해야할까요? 4중 for문을 사용하면 간단하게 해결할 수 있습니다.

for i in 0..<n {
  for j in i..<n {
    for k in j..<n {
      for l in k..<n {
	print("(\(i), \(j), \(k), \(l)")        
      }
    }
  }
}

하지만 5개, 10개, 100개를 골라야 한다면 어떻게 될까요?

처참한 상황을 막기 위해 재귀적으로 바꿔보죠.
먼저 for문이 하는 일부터 생각해볼까요?

원하는 만큼 수를 선택했으면 출력합니다. 끝입니다.

이제 반복을 위해 무엇이 필요한지 생각해볼까요?

• 원소들의 총 개수

• 더 골라야하는 수

• 지금까지 고른 수

이제 마지막으로 기저 사례를 생각해봅시다.

• 원하는 만큼 선택됐는지 확인합니다. --> 더 이상 선택할 수 있는 수가 없는 경우로 생각할 수 있습니다.

이제 이를 구현해보면,

for pick(n: Int, picked: [Int], toPick: Int) {
  if toPick == 0 { return print("\(picked)") }
  // 고를 수 있는 가장 작은 수
  let smallest = picked.isEmpty ? 0 : picked.last! + 1
  // 가장 작은 수 부터 고를 수 있는 모든 경우를 출력
  for s in s..<n {
    var newPicked = picked
    newPicked.append(s)
    pick(n: n, picked: newPicked, toPick: toPick -1)
  }
}

역시 반복이 많아지는 경우를 생각해본다면 매우 간단한 코드로 구현할 수 있습니다.

 

요약해보면, 역시 재귀의 핵심은 기저사례를 제대로 찾을 수 있는 경우인지 확인하는 일입니다. 기저사례가 있는 반복수행이 가능한 일이여만 재귀적으로 수행할 수가 있습니다. 그래야 명확한 종료시점까지 같은 일을 반복할 수 있기 때문이죠.

 

감사합니다. 이번 포스팅은 알고리즘 문제해결전략의 설명이 너무 좋아 많이(거의) 참고해서 사용했습니다.

 

 

 

참고: 종만북 (알고리즘 문제해결전략)