요약

• 재귀 함수는 내부에서 자기 자신을 호출하는 함수를 의미합니다.
• 메모화는 한 번 계산한 값을 저장해 놓은 후 이후에 다시 계산하지 않고 저장된 값을 활용하는 테크닉입니다.
• 조기리턴은 함수의 흐름 중간에 return키워드를 사용해서 코드 들여쓰기를 줄이는 등의 효과를 가져오는 테크닉 입니다.

---

재귀함수

내가 궁금했던 내용을 질문한 댓글을 가져왔다.
Q. 재귀함수의 경우 어째서 for를 사용하지 않았는데도 계속 반복하는지 이해가 잘 안되네요.

A. 함수 내에서 또 함수를 호출하기 때문에 반복처럼 동작합니다. 프로그래밍에서 반복을 만드는 것은 크게 반복문, 재귀호출 로 구분할 수 있습니다!
return 으로 반복하는게 아니라 함수 내부에서 함수를 호출해서 반복되는 것입니다.

팩토리얼 구하기

팩토리얼 연산자 두가지 방법으로 구하기

1. 반복문으로 팩토리얼 구하기

# n! = 1*2*3* ... *(n-2)*(n-1)*n
def function_1(n) :
    output = 1
    for i in range(1, n+1) :
        output *= i
    return output

function_1(5)
120

2. 재귀함수로 팩토리얼 구하기

• n! = n * (n-1)!
• 0! = 1

def factorial_2(n) :
    # n이 0이라면 1을 리턴
    if n == 0 :
        return 1
    # n이 0이 아니라면 n*(n-1)!을 리턴
    else :
        return n * factorial_2(n-1)   # 함수 내부에서 함수를 호출하는 것을 재귀함수라고 한다
    
print(factorial_2(5))
120

피보나치 수열 구하기

피보나치 수열이란
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

f(3) = f(1) + f(2) = 2
f(4) = f(2) + f(3) = 3
f(5) = f(3) + f(4) = 5

즉, f(1) = 1, f(2) = 1, f(n) = f(n-1) + f(n-2)

재귀함수로 구현한 피보나치 수열

def f(n) :
    if n == 1 or n == 2 :
        return 1
    else :
        return f(n-1) + f(n-2)
    
print(f(1))
print(f(2))
print(f(3))
print(f(4))
print(f(5))
1
1
2
3
5

이런식으로 구하게되면 print(f(50))정도면 1시간이 넘게 걸림.... 너무 계산 시간이 오래걸린다는 문제가 있음 그래서 해결하기 위해 메모화라는 것을 사용함!

현재 문제는 같은 값을 구하는 연산을 반복하고 있기 때문에 발생하는것임
따라서 같은 값을 한 번만 계산하도록 코드를 수정해주어야 함

메모화

# 메모 변수를 만듭니다.
메모 = {1:1, 2:1}
# 함수를 선언합니다
def f(n) :
    # 메모가 되어 있으면 메모된 값을 리턴
    if n in 메모 :
        return 메모[n]
    else :
        # 메모가 되어있지 않으면 값을 구함
        output = f(n-1) + f(n-2)
        메모[n] = output
        return output
    
print(f(40))
102334155

print(메모)
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040, 31: 1346269, 32: 2178309, 33: 3524578, 34: 5702887, 35: 9227465, 36: 14930352, 37: 24157817, 38: 39088169, 39: 63245986, 40: 102334155}

---

조기 리턴

return을 중간에 사용하는 형태
들여쓰기 단계가 줄기 때문에 코드를 더 쉽게 읽고 쓸 수 있다. 이렇게 흐름 중간에 return 키워드를 사용하는 것을 조기리턴이라고 부릅니다.
조기에 리턴해서 이후 함수 실행을 차단하는 기술 = 조기 리턴

def f(n) :
    if n in dict :
        return dict[n]  # if 구문 마지막에서 리턴1
    else :
        output = f(n-1) + f(n-2)
        dict[n] = output
        return output  # else 구문 마지막에서 리턴 2

위 코드를 조기 리턴으로 바꾸어 본다.

def f(n) :
    if n in dict :
        return dict[n]  # if 구문 중간에서 리턴이 일어남!
    output = f(n-1) + f(n-2)
    dict[n] = output
    return output

조금 더 알아보기1. 코드에 이름 붙이기
가독성: 코드를 쉽게 읽을 수 있는 성질
가독성이 좋은 코드는 쉽게 읽을 수 있다는 의미
1 ) 주석 달기
2 ) 함수 쓰기: 함수 이름 = 코드 행위 이름 넣기, 한 줄이라도 의미가 있으면
함수로 만들어 사용하면 좋음

조금 더 알아보기 2. 코드 유지보수
고정된 상수는 모두 이름을 붙여서 사용하는 것이 좋음
ex> 3.14로 바로 쓰지 말고 PI = 3.14로 쓰기

---

확인문제

1번 다음 빈칸을 재귀함수로 만들어거 리스트를 평탄화하는 함수를 만들어보세요. 리스트 평탄화는 중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트로 만드는 것을 의미합니다.

def flatten(data) :
    output = []
    for item in data :
        if type(item) == list :
            output += flatten(item)
        else :
            output += [item]
    return output

example = [[1,2,3], [4,[5,6]], 7,[8,9]]
print("원본 :", example)
print("변환 :", flatten(example))
원본 : [[1, 2, 3], [4, [5, 6]], 7, [8, 9]]
변환 : [1, 2, 3, 4, 5, 6, 7, 8, 9]

실행 결과
원본 : [[1,2,3], [4,[5,6]], 7,[8,9]]
변환 : [1, 2, 3, 4, 5, 6, 7, 8, 9]

이 문제를 출 때는 리스트의 데이터가 리스트인지 아닌지를 구분할 수 있어야 합니다. type()함수를 사용해서 자료형을 판변할 때는 다음과 같은 코드를 사용합니다.

type(10) == int
True
type("10") == str
True
type([]) == list
True

코드 풀이

def flatten(data) :
# 2) data = example = [[1,2,3], [4,[5,6]], 7,[8,9]]
# 6) flatten([1, 2, 3])
# 11) flatten([4, [5, 6]])
    output = []
    for item in data :
        # 3) [1, 2, 3]
        # 3) [4, [5, 6]]
        # 3) 7
        # 3) [8, 9]
        # 7) 1, 2, 3
        # 12) 4, [5, 6] ...... 이런식으로
        if type(item) == list :
        # 4) if type([1, 2, 3]) == list
        # 9) if type ([4,[5, 6]]) == list
            output += flatten(item)
            # 5) [] += flatten([1, 2, 3])
            # 10) [1, 2, 3] += flatten([4, [5, 6]])
        else :
            output += [item]
            # 8) [] += [1, 2, 3]
    return output

example = [[1,2,3], [4,[5,6]], 7,[8,9]]
# 1) 리스트 할당
print("원본 :", example)
print("변환 :", flatten(example))

2번 패밀리 레스토랑에서 여러 개의 테이블에 나누어 앉으려고 합니다.

이때 한사람만 앉는 테이블이 없게 그룹을 지어야 합니다. 인원 수를 나누는 패턴만 구하면 되며, 누가 어디에 앉는지 등은 고려하지 않아도 괜찮습니다. 한 개의 테이블에 앉을 수 있는 최대 사람의 수는 10명입니다. 100명의 사람이 하나 이상의 테이블에 나누어 앉는 패턴을 구하세요.

앉힐수있는최소사람수 = 2
앉힐수있는최대사람수 = 10
전체사람의수 = 100
memo = {}

def 문제(남은사람수, 앉힌사람수) :
    key = str([남은사람수, 앉힌사람수])
    # 종료 조건
    if key in memo :
        return memo[key]
    if 남은사람수 < 0 :
        return 0
    if 남은사람수 == 0 :
        return 1
    # 재귀 처리
    count = 0
    for i in range(앉힌사람수, 앉힐수있는최대사람수 + 1) :
        count += 문제(남은사람수 - i, i)
    # 메모화 처리
    memo[key] = count
    # 종료
    return count

print(문제(전체사람의수, 앉힐수있는최소사람수))
437420