[React] 재귀 알고리즘 (Recursive Algorithms)

재귀 알고리즘이란?

• 같은 알고리즘을 반복하여 사용하며 문제를 푸는 방법이다.
• 특정 알고리즘 이름이 아닌 하나의 방법을 말하는 것이다.

재귀 호출의 종결 조건

• 재귀 알고리즘을 사용하기 위해서는 해당 호출의 종결조건(Trival case)이 중요한다.
• 만약 종결조건을 지정하지 않는다면 무한하게 알고리즘을 호출하기 때문이다.

def sum(n):

	# 종결조건
	if n <= 1:
		return 1

	# 종결조건에 부합하지 않는 경우 재귀 호출
	else:
		return n + sum(n-1)

# 4 + 3 + 2 + 1
# 10 출력
print(sum(4))

• 재귀 호출의 형태(Recursive version)에는 그에 대칭되는 반복적인 형태(Iterative version)이 존재한다.
• 둘은 복잡도는 동일하지만, 문제에 따라 서로 효율적인 경우가 다르다.
• 하지만, 반복적으로 동일한 함수를 많이 호출하기 때문에 효율성 측면에서는 재귀 호출이 불리한 경우가 많다.

하노이의 탑

def hanoi(n, start, end, temp):

    # n이 1일때는 바로 도착 지점으로 옮기면 된다.
    if n == 1:
        print(f"{start} -> {end}")

    # n이 1보다 클 경우
    else:
        # end 기둥을 temp 기둥으로 사용하여 n-1개의 원판을 temp 기둥으로 옮긴다.
        hanoi(n - 1, start, temp, end)

        # 위 과정을 거치면, start에는 1개의 원판(가장 마지막 원판)만 남으며, 이 원판을 end 기둥으로 옮긴다.
        print(f"{start} -> {end}")

        # 이제 temp 기둥에 있는 n-1개의 원판을 start 기둥을 temp 기둥으로 사용하여 end로 옮긴다.
        hanoi(n - 1, temp, end, start)

# start -> 1번 기둥
# temp -> 2번 기둥
# end -> 3번 기둥
# n(원판 갯수) -> 5개
hanoi(5, 1, 3, 2)