September 14, 2022

1. 팩토리얼

1.1 정의

팩토리얼은 1부터 n까지 연속한 숫자를 차례로 곱한 값입니다.

아래는 팩토리얼을 이해하기 위한 예시 입니다.

	1! = 1
	2! = 1 × 2 = 2
	3! = 1 × 2 × 3 = 6
	n! = 1 × 2 × 3 × … × (n -1) × n
	단, 0!은 1이라고 약속합니다.

1.2 코드구현

	# 입력: n
	# 출력: 1부터 n까지 연속한 숫자를 곱한 값

	def factorial(n):
		num = 1                        # 곱을 계산할 변수
		for i in range(1, n + 1):      # 1부터 n까지 반복(n + 1은 제외)
			num = num * i              # 곱셈 연산으로 수정
		return num

	print(factorial(1))                 # 1! = 1
	print(factorial(5))                 # 5! = 120
	print(factorial(10))                # 10! = 3628800

2. 재귀호출

2.1 정의

재귀 호출(recursion)은 어떤 함수 안에서 자기 자신을 부르는 것을 말합니다.

2.2 코드구현

	# 1부터 n까지의 합을 재귀호출을 이용하여 표현

	def sumByRecursion(n):
		if n < 1:
			return n
		n = n + sumByRecursion(n - 1)
		return n

	if __name__ == '__main__':
			result = sumByRecursion(3)
			print(result)

	# 숫자 n개 중에서 최댓값을 찾는 재귀 호출

	numList = [1, 3, 5, 6]
	maxValue = numList[0]
	def getMaxValue(numLength,maxValue):
	numLength = numLength - 1
	if numLength < 1:
		return maxValue
	maxValue = maxValue if maxValue >= numList[numLength]  else numList[numLength]
	getMaxValue(numLength,maxValue)
	return maxValue

	print(getMaxValue(len(numList),maxValue))

#피보나치 수열을 재귀 방식으로 구현

def fibonacci(n):
    if n <= 1:
        return n

    n = fibonacci(n - 2) + fibonacci(n - 1)
    return n


print(fibonacci(6))

3. 하노이의 탑

3.1 정의

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다.
세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

한 번에 한개의 원판만 옮길 수 있습니다.
가장 위에 있는 원판만 이동할 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나입니다.

3.2 코드구현

#하노이의 탑 구현

	def hanoi(frm, to, n, count):

		if n == 1:
			print(f'{frm} {to} : {count}')
			return 1
		else:
			empty = 6 - frm - to
			count += hanoi(frm, empty, n - 1, count)
			print(f'{frm} {to}: {count}')
			count += hanoi(empty, to, n - 1, count)

		return count


	print('원반의 개수: ')
	numberOfDisk = int(input())
	print('원반들의 시작 위치: ')
	startLocation = int(input())
	print('옮겨야 할 위치: ')
	desLocation = int(input())
	print('\n')
	totalCount = hanoi(startLocation, desLocation, numberOfDisk, 0)
	print(f'총 이동 횟수: {totalCount}')