알고리즘 1: 재귀함수

def sum_func(n):
	# Base Case: 종료 부분
	if n = 1:
    	return 1
        
    # Recursive Case: 자기 자신을 호출하는 부분
    return sum_func(n-1) + n

Base Case와 Recursive Case가 함께 있지 않으면 재귀함수가 아니다.

단, 재귀함수는 함수 호출을 반복하면서 '이미 구한 값을 또 구하면서' 시간 복잡도가 증가할 수 있다.
그러므로 한번 구한 값은 저장해 불필요한 중복 계산을 피하는 것이 좋다. -> 메모이제이션

핵심: f(n)과 f(n-1)의 관계를 찾아 나타낼 수 있느냐!

위의 sum_func(n) 함수는 f(n) = f(n-1) + n의 관계

피보나치 함수

-> 가장 대표적인 재귀문제 '피보나치 함수'는 f(n) = f(n-1) + f(n-2)의 관계.

n = int(input())

fibo_list = [-1] * (n + 2)    # list 공간은 미리 확보해두어야 함. (2개의 초기값이 있으므로 n+2개 공간 확보)
fibo_list[0] = 0
fibo_list[1] = 1    # 메모이제이션을 위해 각 결과를 list에 저장

def fibo(n):
	
	global fibo_list

	if fibo_list[n] != -1:
		return fibo_list[n]    # 이미 답을 한 번 구했다면 저장한 답을 return

	fibo_list[n] = fibo(n-1) + fibo(n-2)     # 구한 답은 list에 저장한 다음 return
	return fibo_list[n]

print(fibo(n))

칸토어 집합

-> 이 문제는 [문자열] f(n) = f(n-1) + ' ' * (3 ** (n-1)) + f(n-1)의 관계.

def sol(n):
    if n == 0:
        return('-')
    return(sol(n-1) + ' ' * pow(3,(n-1)) + sol(n-1))

while True:
    try:
        N = int(input())
        print(sol(N))
    except:
        break

(+) 다른 풀이

ans = [' ' for i in range(13)]    # 문제의 최대만큼 공간 확보
ans[0] = '-'

# 미리 만들어놓기 -> ans[12]까지!
for i in range(12):
	ans[i+1] = ans[i] + (' ' * (3 ** i)) + ans[i]
    
while True:
    try:
        N = int(input())
        print(ans[N])
    except:
        break