📒 재귀 알고리즘(Recursive Algorithm)

📌 재귀함수

• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
• 많은 종류의 문제를 재귀적으로 해결 가능하다.
  ex) 이진 트리(Binary Tree)

📙 실습 1 - 자연수의 합 구하기(1~n까지 모든 자연수의 합)

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

📙 실습 2 - Factorial(1~n까지 모든 자연수의 곱)

def Factorial(n):
	if n<=1: return 1
    else: return n*Factorial(n-1)

📙 실습 3 - Fibonacci 순열

Iterative

def Fibonacci_While(x):
	if x<=1: return x
    Fibo = [0, 1]
    i = 2
    while n<=x:
    	Fibo.append(Fibo[i-1]+Fibo[i-2])
        i+=1
    return Fibo[x]

def Fibonacci_for(x):
	if x<=1: return x
    Fibo = [0, 1]
    for i in range(2, x+1):
    	Fibo.append(Fibo[i-1]+Fibo[i-2])
    return Fobo[x]

Recursive

def Fibonacci_Recursive(x):
	if x<=1: return x
    else:
    	num = Fibonacci_Recursive(x-1)+Fibonacci_Recursive(x-2)
    return num

📙 실습 4 - 조합의 수
1. Math 라이브러리 사용

from math import factorial as F
def Combination(n, m):
	return F(n)/F(m)*F(n-m))

2. Recursive

def Combination(n, m):
	if n==m or m==0: return 1
    else:
    	return Combination(n-1, m) + Combination(n-1, m-1)

📙 실습 5 - 하노이의 탑

def Top_of_Hanoi(n, Start, End, Sup):
	if n==1:
    	print("원반이 1개입니다. ",Start,"에서 ", End, "로 이동했습니다.")
    	return
    Top_of_Hanoi(n-1, Start, Sup, End)
    print("원반", n, "을", Start, "에서", End, "로 옮깁니다.")
    Top_of_Hanoi(n-1, Sup, End, Start)

Top_of_Hanoi(3, 'A', 'C', 'B')

📙 실습 6 - 재귀적 이진 탐색

def Binary_Search(L, x, lower, upper):
	if lower>upper: return -1
    mid = (lower+upper)//2
    
    if x==L[mid]: return mid
    elif x<L[mid]:
    	return Binary_Search(L, x, lower, mid-1)
    else:
    	return Binary_Search(L, x, mid+1, upper)