PYTHON - 재귀 함수 (피보나치, 하노이의 탑, 최소공배수 등)

재귀함수 (recursion)

• 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
• 반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
• 같은 행위가 반복될 때 재귀함수를 사용한다.

---

순차탐색

def search(li, begin, end, target): 
	if begin > end: 
		return -1 
	elif target == li[begin]: 
		return begin 
	else: 
		return search(li, begin+1, end, target)

li = [1,6,10,7,2,5]
target = 10
search(li, 0, 5, 10) # 2

 

2진수 변환

def print_binary(n): 
	if n < 2: 
		print(n, end='') 
	else: 
		print_binary(n // 2) 
		print(n % 2, end = '')

print_binary(15) #1111

 

배열의 합

• li[0]에서 li[n-1] 까지의 합을 구하여 리턴
• 재귀적 사고방식: li[n-1] + (li[n-2] 까지의 합) 을 구한다

def sum(n, li): 
	if n <= 0 or n >= len(li): 
		return 0 
	return li[n - 1] + sum(n - 1, li)

 

0~n 까지의 합계 구하기

def sum(n): # 이 함수의 목표는 0~n 까지의 합을 구하는 것이다
	if n == 0: # n=0 이면 합은 0이다
		return 0 
	return n + sum(n - 1) # n이 0보다 크면 0에서 n 까지의 합은, n-1까지의 합에 n을 더한 것이다.

sum(4) # 10

 

1~n 까지의 곱 구하기

def factorial(n): 
	if n == 0: 
		return 1 
	return n * factorial(n-1)

factorial(4)

 

x^n 구현

def power(x, n): 
	if n == 0: 
		return 1 
	return x * power(x, n - 1)

power(2,10) # 1024

 

피보나치 수열

# 피보나치 수열의 index n의 값을 리턴# 피보나치 수열 : 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
def fibo(n): # 재귀함수는 탈출조건이 꼭 필요하다.
	if n == 0 or n == 1: 
		return 1 
	return fibo(n - 2) + fibo(n - 1)

# index n까지의 피보나치 수열 구하기
def fibo_list(n): 
	for i in range(n): 
		print(fibo(i), end = " ")

 

최대공약수 (유클리드 호제법)

def gcd(m, n): 
	if m < n: 
		m, n = n, m 
	if m % n == 0: 
		return n 
	else: 
		return gcd(n, m % n)
print(gcd(48, 60)) # 12

• 참고: 두수의 곱을 최대공약수로 나누면 최소공배수가된다.

 

하노이 타워

• A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다.
• A에 남은 하나의 원반을 C로 옮긴다.
• B의 모든 원반을 C로 옮긴다.

def hanoi(num, _from, _by, _to): #탈출 조건
	if num == 1: 
		print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num)) 
	return hanoi(num-1, _from, _to, _by) 
	print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num)) hanoi(num-1, _by, _from, _to)

if __name__ == "__main__": 
	while 1: 
		numOfTray = int(input("원반의 개수를 입력하세요!(종료 : 0) :")) 
		if numOfTray == 0: 
			break
		
hanoi(numOfTray, 'A', 'B', 'C')