1-2. [구현] 재귀

재귀함수의 매개변수 선언순서에 규칙을 주자 => 입력, 출력, 내부변수

 

1. 팩토리얼

 

# 재귀... O(N)

def fact(n):
    if n == 1:
        return 1

    return n * fact(n - 1)


print(fact(3))

 

2. 최대공약수

 

# 재귀... O(logN)

def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)


print(gcd(9, 6))

 

3. 하노이탑

 

# 재귀... O(2^N)

def hanoi(n, from_p, to_p, aux_p):
    if n == 1:
        print(f"{from_p} -> {to_p}")
        return

    hanoi(n - 1, from_p, aux_p, to_p)
    print(f"{from_p} -> {to_p}")
    hanoi(n - 1, aux_p, to_p, from_p)


hanoi(2, 1, 3, 2)

 

4. 중복선택하는 경우의 수 (중복순열)

• ["1", "2"] 원소 2개를 2번 중복선택하면 => ["1", "1"], ["1", "2"], ["1", "3"], ["2", "2"] 모두 4개이다 

 

# 재귀... O(N^2)
#
# 재귀함수의 매개변수 선언순서에 유의하자 => 입력, 출력, 내부변수

def recursive(data, repeat, rst, a):
    if repeat == 0:
        rst.append(a[:])
        return

    for x in data:
        a.append(x)
        recursive(data, repeat - 1, rst, a)
        a.pop()


rst = []
recursive(["1", "2"], 2, rst, [])
print(rst)


# 사용하기 쉽게 변경

def solution(data, repeat):
    result = []

    def recursive(a, level):
        if level == repeat:
            result.append(a[:])
            return

        for x in data:
            a.append(x)
            recursive(a, level + 1)
            a.pop()

    recursive([], 0)
    return result


print(solution(["1", "2"], 2))