[알고리즘] 재귀 (Recursion)

재귀

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

🚀 절차 지향적 사고와 귀납적 사고

• QUESTION: n부터 1까지 출력하는 문제

 

절차 지향적 사고

• func1(3)의 출력 결과가 왜 3 2 1인지를 생각해본다면 이 코드가 동작하는 흐름을 그대로 따라가면 된다.
• 일단 func1(3)가 호출되면 3을 출력하고 func1(2)를 호출한다. func1(2)는 2를 출력한 후에 func1(1)을 호출할거고 func1(1)은 1을 출력한 후에 func1(0)을 호출한다. 그리고 func1(0)은 02번 줄에 걸려서 종료된다. 이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다.

귀납적 사고

• 첫 번째로 func1(1)이 1을 출력한다, 이건 굉장히 자명하다.
• func1(k)가 k k-1 k-2 … 1을 출력하면, 즉 k부터 1까지 차례대로 출력하면 func1(k+1)은 k+1부터 1까지 차례로 출력한다는걸 보여야 한다.
• 이걸 보이는건 func1(k+1)이 호출될 때 어떤 상황이 생기는가를 보면 되는데 k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는 k부터 1까지 차례로 출력한다 가정을 했으니 func1(k+1)은 k+1부터 1까지 차례대로 출력함을 알 수 있다.
• 이 두 문장이 참이므로 귀납적으로 func1 함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 된다.

재귀 함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.
• 모든 입력은 base condition으로 수렴해야 한다.
• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
• 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 볼 수 있다.

기타

• 직접 함수를 호출하기, 케이스 별로 찢어지는 경우
• 반복문 주의하기

 

---

예시 문제들

🚀 예제 문제 및 해결

• BOJ 1629번: 곱셈
• 1승을 계산할 수 있다.
• k승을 계산 했으면 2*K 승과 2*k + 1 승도 O(1)에 계산할 수 있다.
• a의 임의의 지수승을 귀납적으로 계산할 수 있다.

def pow(a, b, c):
    if b == 1:
        return a % c
    value = pow(a, b // 2, c)
    value = (value * value) % c
    if b % 2 != 0:
        value = value * a % c
    return value


A, B, C = map(int, input().split())
print(pow(A, B, C))

 

• BOJ 11729번: 하노이 탑 이동순서

def hanoi(n, start, end, result):
    if n == 1:
        result.append((start, end))
        return
    hanoi(n - 1, start, 6 - start - end, result)
    result.append((start, end))
    hanoi(n - 1, 6 - start - end, end, result)


result = []
N = int(input())
hanoi(N, 1, 3, result)

print(len(result))
for (i, j) in result:
    print(f'{i} {j}')

 

• BOJ 1074번: Z

def func(n, r, c):
    if n == 0:
        return 0
    half = 1 << (n-1)
    if r < half and c < half:
        return func(n-1, r, c)
    if r < half and c >= half:
        return half*half + func(n-1, r, c-half)
    if r >= half and c < half:
        return 2*half*half + func(n-1, r-half, c)
    return 3*half*half + func(n-1, r-half, c-half)


n, r, c = map(int, input().split())
print(func(n, r, c))

 

• BOJ 17478번: 재귀함수가 뭔가요?

def recursion(n, step):
    if n == 0:
        print(f'{"____" * step}"재귀함수가 뭔가요?"')
        print(f'{"____" * step}"재귀함수는 자기 자신을 호출하는 함수라네"')
        print(f'{"____" * step}라고 답변하였지.')
        return
    print(f'{"____" * step}"재귀함수가 뭔가요?"')
    print(f'{"____" * step}"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
    print(f'{"____" * step}마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
    print(f'{"____" * step}그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
    step += 1
    recursion(n - 1, step)
    print(f'{"____" * (step - 1)}라고 답변하였지.')


N = int(input())
print('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.')
recursion(N, 0)

---

 

[바킹독의 실전 알고리즘] 내용을 기반으로 정리한 포스팅입니다.