🙂 재귀 알고리즘(하노이의 탑)

🙂 재귀 함수(Recursion Function)

• 재귀 함수란 함수 내부에서 자기 자신을 또 다시 호출하는 함수를 뜻한다.
• 재귀 함수는 자기가 자신을 계속해서 호출하므로 호출을 중단할 조건문을 반드시 포함해야 한다.

🙂 소스 코드(python)

def function(입력값):
    if 입력값 > 제한값:
        return function(입력값-1)
    else:
        return 제한값 또는 특정값

🙂 예제1) 팩토리얼

n = 5
def factorial(n):
    if(n == 0):
        return 1
    if(n == 1):
        return 1
    return n * factorial(n-1)
print(factorial(n))            // 120

🙂 예제2) 피보나치 수열

n = int(input())
def fibonacci(n):
    if(n <= 1):
        return n
    return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(n))    

🙂 예제3) 하노이의 탑

N = int(input())
def hanoi(N, start, end):
    if (N == 1):
        print(start, end)
        return
    hanoi(N-1, start, 6-start-end)
    print(start, end)
    hanoi(N-1, 6-start-end, end)
print(2**N-1)
hanoi(N, 1, 3)