재귀

recursion

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)

for문을 활용하여 단순하게 *= 할 수 있지만, 재귀적으로 가능하다.

import sys		# 백준 1914번 - 하노이 탑

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

# height층의 탑을 a 에서 b 로 옮기기
trace_plate = []
mul = 1
ans = 0 # 정답

# 가장 아래판을 남기고 빈 곳으로 이동 > 아래판 이동 > 다시 하노이.
def hanoi(height, a, b):
    if height>1: hanoi(height-1, a, 6-a-b)
    trace_plate.append(str(a)+' '+str(b))
    if height>1: hanoi(height-1,6-a-b,b)

if n <=20:
    hanoi(n, 1, 3)
    print(len(trace_plate))
    for x in trace_plate:
        print(x)
else:
    for x in range(1, n+1):
        ans += mul
        mul *= 2
    print(ans)

재귀적으로 반복되는 큰 틀을 정한 뒤, 마지막에 빠져나올 도착지를 확보한다.

import sys		# 백준 9663번 - Nqueen

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

b = 0 # 정답

d = [False] * n 		# 각 행에 퀸이 놓였는지
e = [False] * (n*2 - 1) # 우상향 대각선에 몇번째 대각선에 퀸이 놓였는지
f = [False] * (n*2 - 1) # 우하향 대각선에 몇번째 대각선에 퀸이 놓였는지

def queen(x):
    for y in range(n):
        if (not d[y]) and (not e[x+y]) and (not f[n-1+x-y]):
            if x == n-1:
                global b
                b += 1
            else:
                d[y] = True
                e[x+y] = True
                f[n-1+x-y] = True
                queen(x+1)
                d[y] = False
                e[x+y] = False
                f[n-1+x-y] = False

queen(0)
print(b)

열당 하나를 놓는 반복에서, 행과 두 대각선에 놓인 여부를 확인하며 재귀로 채워나간다.

import sys		# 백준 1074번 - Z

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

a = 2 ** n
b = q + 1
c = r + 1
d = -1 # 저장용

def get(x, y, z):               # 몇 행, 몇 열, 변의 길이
    global d
    if z != 2:
        if x <= z/2 and y <= z/2:   # 왼위
            get(x, y, z/2)
        if x > z/2 and y <= z/2:    # 오위
            d += ((z/2) ** 2)
            get(x-z/2, y, z/2)
        if x <= z/2 and y > z/2:    # 왼아
            d += ((z/2) ** 2)*2
            get(x, y-z/2, z/2)
        if x > z/2 and y > z/2:     # 오아
            d += ((z/2) ** 2)*3
            get(x-z/2,y-z/2,z/2)
    
    else:
        if x == 1 and y == 1: d += 1
        if x == 2 and y == 1: d += 2
        if x == 1 and y == 2: d += 3
        if x == 2 and y == 2: d += 4

get(b, c, a)
print(int(d))

숫자의 방향이 정해졌을 때, 큰 4조각의 순서를 행하고 변의길이를 반으로 줄여 그 속의 4조각을 다시 확인한다.