🚶‍♂️Road to 코테(10) - 재귀

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

재귀

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

간단한 재귀함수

재귀로 N부터 1까지 출력하는 함수와 1부터 N까지의 합을 구하는 함수 짜보기

import sys


def print_recur(n):
  if n<0:
    return
  print(n)
  n-=1
  print_recur(n)
  
def summ(n):
  
  if n<0:
    return 0
  else:
    return n+summ(n-1)
    
    
n=int(sys.stdin.readline())
print_recur(n)
sres=summ(n)

print(sres)

우리가 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결한다는 것.

-> 여기서 귀납적인 것은 상식과는 큰 차이가 있다.

도미노를 쓰러트릴 때 왜 모든 도미노가 쓰러질까?

1. 1번부터 N번까지 모든 도미노가 쓰러진다.
2. 수학적 귀납법 이용
   • 1번 도미노가 쓰러진다
   • k번 도미노가 쓰러진다
   • k+1번 도미노가 쓰러진다
     가 모두 참이므로 모든 도미노가 쓰러진다
     = 결국 1번 설명과 같지만 절차지향형이 아닌 수학적 귀납법으로서 쓰러지는 것이다.

n부터 1까지 차례로 출력하는 함수(func1)를 수학적 귀납법으로 설명하면
func(1)이 1을 출력하면 func(k)가 k,k-1,k-2, ... 1을 출력하므로 func(k+1)은 k+1부터 1까지 차례대로 출력한다.
-> 이는 func(k+1)이 호출되었을 때 k+1이 출력된 후 k부터 1까지 출력하는 func(k)를 호출되기 때문이다.

이 두 문장이 참이므로 귀납적 방식으로 인해 func()가 n부터 1까지 차례로 출력하는 함수인 것을 알 수 있다.

조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.
모든 입력은 base condition(base case)으로 수렴해야한다.
ex) n=0일 때 자기 자신을 호출하지 않고 종료가 되니 이것이 base condition이다.

정보

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

구현을 할 때 3가지를 지켜야 한다.
1. 함수의 정의
2. base condition
3. 재귀 식

연습 문제 1 - 거듭 제곱

import sys

a,b,c=map(int,sys.stdin.readline().split())

def recur(a,b):
  
  if b==1:
    return a%c
  else:
    tmp=recur(a,b//2)
    if b%2==0: #base condition
      return (tmp * tmp )%c 
    else:		#base condition
      return (tmp * tmp*a)%c

print(recur(a,b))  

만약 a^10일 때, (a^5) x (a^5)와 같다.
b가 11같은 홀수 일경우 (a^b/2) x (a^b/2) x a이다.
시간 복잡도가 절반씩 깎이기 때문에 O(logb)이다.

연습문제 2 - 하노이 탑

import sys

k=int(sys.stdin.readline())

# 2 번 원판이 가려면 이동이 3번이 필요하고
# 3 번 원판이 가려면 이동이 7번 필요하다.
# 옮긴 횟수는 2k+1
# N 번째 원판이 가려면 N-1번까지의 원판이 먼저 기둥 2에 가야한다
# N 번째 원판을 기둥 3에 옮기고 다시 n-1원판을 기둥 3으로 옮긴다.
# 원판이 1개면 원하는 곳에 옮길 수 있다. 그렇다면 K+1개도 내가 옮길 수 있다. 



def hanoi(a,b,n): 
  # 원판 N개를 기둥 a에서 b로 옮기는 방법을 출력하는 함수
  """
  재귀식
  n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다
  n번의 원판을 기둥 a에서 기둥 b로 옮긴다.
  n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.
  """
  if n==1:
    print(a,b)
    return
  
  hanoi(a,6-a-b,n-1)
  print(a,b)
  hanoi(6-a-b,b,n-1)

print(2**k-1)
hanoi(1,3,k)

연습문제 3 - Z

• 함수의 정의 : 2^n x 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수
• base condition : n=0 일때 (방문할 2x2가 없을때) return
• 재귀 식
  (r,c)가 1번 사각형일 때 return recur(n-1,r,c)
  (r,c)가 2번 사각형일 때 return halfxhalf + recur(n-1,r,c-half)
  (r,c)가 3번 사각형일 때
  (r,c)가 4번 사각형일 때

import sys

def recur(n,r,c):
  if n==0:
    return 0
  half=2**(n-1)	# 4개짜리 사각형 몇개 인지
  if r<half and c<half: # 왼쪽 위
    return recur(n-1,r,c)
  if r<half and c>=half: # 오른쪽 위
    return (half*half)+recur(n-1,r,c-half) 
  if r>=half and c<half: # 왼아래
    return (2*half*half)+recur(n-1,r-half,c)
  else:                  # 오른 아래
    return (3*half*half)+recur(n-1,r-half,c-half)

  


n,r,c=map(int,sys.stdin.readline().split())

print(recur(n,r,c))

재귀 in Java

재귀(Recursion)는 큰 문제를 동일한 유형의 더 작은 문제로 나누어 해결하는 방식입니다.
재귀 함수는 자기 자신을 호출하여 반복적으로 더 작은 문제를 해결하고, 이 과정을 통해 원래 문제를 해결합니다.

단순한 개념 같지만, 재귀는 완전탐색, 동적 계획법(DP), 그래프 탐색(DFS), 트리 순회 등 다양한 알고리즘 문제에서 핵심 도구로 사용됩니다.

1. 재귀의 핵심 구성 요소

1. Base Case (기저 조건)
   더 이상 문제를 쪼갤 수 없거나, 답이 명확해지는 종료 조건입니다.

Base Case가 없으면 재귀는 무한히 호출되어 StackOverflowError(RecursionError)가 발생합니다.

2. Recursive Call (재귀 호출)
   문제를 더 작은 문제로 나누고, 이를 해결하기 위해 자기 자신을 호출합니다.

2. 자바 재귀 예시

2-1. 팩토리얼 (factorial)
팩토리얼은 1부터 n까지의 정수를 곱한 값입니다.

public static int factorial(int n) {
    if (n == 1) { // Base Case
        return 1;
    }
    return n * factorial(n - 1); // Recursive Call
}

실행 과정 예시
factorial(4)를 호출하면:

factorial(4) -> 4 * factorial(3)
factorial(3) -> 3 * factorial(2)
factorial(2) -> 2 * factorial(1)
factorial(1) -> 1  (Base Case)

2-2. 피보나치 (fibonacci)
피보나치 수열은 앞 두 항의 합이 다음 항이 되는 수열입니다.'

public static int fibo(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

fibo(5) -> fibo(4) + fibo(3)
fibo(4) -> fibo(3) + fibo(2)
fibo(3) -> fibo(2) + fibo(1) = 1 + 1

3. 재귀의 시간 복잡도

재귀의 시간복잡도는 정확히 계산하기 어렵지만, 대략적으로는
재귀 함수 호출 수 × (재귀 함수 하나당 시간복잡도)로 계산할 수 있습니다.

4. 재귀 사용 시 주의사항

1. 무한 루프 방지
   기저 조건이 없으면 무한 루프에 빠질 수 있으니, 종료 조건을 반드시 명확히 정의해야 합니다.
   기저 조건이 명확하지 않더라도, 재귀 호출을 제한할 수 있는 조건문을 통해 자연스럽게 멈추는 상황을 만들어야 합니다.
   예시: DFS에서 방문 체크

public static void dfs(int cur) {
    visited[cur] = true;
    for (int next : graph.get(cur)) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

if (!visited[next]) 조건문은 재귀 호출을 제한하는 필터 역할을 합니다.
방문되지 않은 노드만 재귀 호출하도록 제어하므로, 무한 루프를 방지합니다.
하지만 이 조건이 명시적인 기저 조건은 아니므로, 기저조건으로 간주하긴 어렵습니다.

2. 재귀 깊이와 대안 고려

• 재귀 깊이를 너무 크게 설정하지 말 것
  재귀 깊이가 너무 크면 메모리 초과(OutOfMemoryError)가 발생할 수 있습니다.
  대부분의 경우 10,000 정도면 충분합니다.

• 대안이 있는지 고려
  입력 크기가 재귀 제한을 초과한다면, 반복문 등 다른 풀이를 시도해 보는 것도 좋은 선택입니다.
  반복문을 활용할 수 있다면, 재귀 대신 반복문을 사용하는 것이 더 안전하고 효율적입니다.