재귀- 바킹독 유튜브를 보고 정리

개념

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

1부터 N까지의 합을 구하는 함수를 한 번 짜보자!

def get_sum_from_one_to_N(n):
    if n == 0: return 0
    return n + get_sum_from_one_to_N(n-1)

어떤 문제를 재귀로 풀겠다는 것은 귀납적 방식으로 해결하겠다는 의미이다. 귀납적 방식은 우리가 일반적으로 알고 있는 상식과 큰 차이가 있다.

도미노가 1 > 2 > 3 > 4 순서대로 쓰러지기 때문에 마지막 도미노도 쓰러진다. 라는 절차지향적 사고가 아니라

1번 도미노가 쓰러진다. > k번째 도미노가 쓰러지면 k+1번째 도미노가 쓰러진다. > 마지막 도미노가 쓰러진다. 처럼 귀납적 사고방식을 해야한다.

재귀 함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 (base condition)
• 모든 입력은 base condition으로 수렴해야함

재귀에 대한 정보

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 본다.
• 한 함수가 자기 자신을 여러번 호출하게 되면 예상과 다르게 비효율적일 수 있다.
• 재귀함수가 자기 자신을 부를 때 스택영역에 계속 누적이 된다.

연습문제

• boj - 1629 base-condition을 잘 잡아뒀고 k승의 결과를 토대로 2k, 2k+1승의 결과를 계산할 수 있으니 마치 도미노를 쓰러뜨리는 것처럼 모든 결과가 잘 계산될 것이다.라고 함수를 이해할 필요가 있다. 시간복잡도는 B값이 계속 절반씩 깎이기 때문에 O(logB)이다.

  A, B, C = map(int, input().split())
  def get_multiple_square_mod(number,square,mod):
      if square == 1:
          return number % mod
      squared_number = get_multiple_square_mod(number, square//2, mod)
      
      squared_number = squared_number * squared_number % mod
      if square % 2 ==0: 
          return squared_number
      return squared_number * number % mod
      
  print(get_multiple_square_mod(A, B, C))

• boj - 11729 https://www.mathsisfun.com/games/towerofhanoi.html → 풀어보기 기존의 절차지향적 사고를 버려야 이 문제를 제대로 풀 수 있다. n번 그러니까 제일 아래에 있는 원판을 중심으로 생각해보면 n -1번째 원판부터 1번째 원판은 기둥 2로 가야한다. 그래야 n번째 원판이 기둥3으로 갈 수 있다.

  1. 함수의 정의

     원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수

  2. base codition

     n = 1일 때 print(f”{start} {end}”

  3. 재귀식

     n-1개의 원판을 기둥 a에서 기둥 6-a-b → 기둥의 숫자 1, 2, 3의 합이 6이므로 6에서 시작값 끝 값을 빼면 중간값이 나온다.
     
     n번 원판을 기둥 a에서 기둥 b로 옮긴다.
     
     n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.

     N = int(input())
     result = []
     def hanoi(start, end, n):
         if n == 1: 
             result.append([start, end])
             return
         hanoi(start, 6-start-end, n-1)
         
         result.append([start, end])
         
         hanoi(6-start-end, end, n-1)
     
     hanoi(1, 3, N)
     print(len(result))
     for value in result:
         print(" ".join(map(str, value)))

• boj-1074

  1. 함수의 정의

     2의n제곱 * 2의n제곱 배열에서 (r,c)를 방문하는 순서를 반환하는 함수

  2. base condition

     n = 0일 때 retrun 0

  3. 재귀식

     half = 한 변 길이의 절반 즉 2의 n-1승
     
     (r, c)가 1번 사각형일 때 return func(n-1, r, c)
     
     (r, c)가 2번 사각형일 때 return half * half + func(n-1, r, c-half)
     
     (r, c)가 3번 사각형일 때 return 2 * half * half + func(n-1, r-half, c)
     
     (r, c)가 4번 사각형일 때 return 3 * half * half + func(n-1, r-half, c-half)

     N, R, C = map(int, input().split())
     def get_z_index(n,r,c):
         if n == 0: return 0
         half = 1 << (n-1)
         if (r < half and c < half): return get_z_index(n-1, r, c)
         if (r < half and c >= half): return half* half + get_z_index(n-1, r, c-half)
         if (r >= half and c < half): return 2 * half * half + get_z_index(n-1, r-half, c)
         return 3 * half* half + get_z_index(n-1, r-half, c-half)
     
     print(get_z_index(N, R, C))

피드백

내가 그동안 재귀를 이해하고 있던 방식을 바꿔주는 계기가 되었다. 절차지향적 사고에서 벗어나 귀납적으로 사고를 해보자.