[Python 기초] 재귀 알고리즘 (recursive algorithms)

#종결조건의 중요성 알아보기

#재귀의 간단한 예시 - 1부터 n까지 sum

def sum(n):
    print(n)
    if n<=1: #이 종결 조건이 없으면 에러 발생 (계속 작아짐)
        return n
    else:
        return n+sum(n-1)

    
a = int(input("Numer:"))
print(sum(a)) 

#In: 4
#Out:
#Numer:4
#4
#3
#2
#1
#10

 

 

#Recursive vs Iterative 복잡도

#recursive
def sum(n):
    if n<=1:
        return n
    else:
        return n+sum(n-1)

#iterative
def sum(n):
	s = 0
    while n >=0:
    	s+=n
        n-=1
	return s

- Recursive와 Iterative 모두 n에 비례하는 복잡도를 가짐 → O(n)

- 그러나 효율성 측면에서는 Recursive가 더 떨어질 수 있음

def sum(n):
    return n*(n+1)//2
#O(1) 복잡도를 가짐

 

 

#Recursive 예제 - n!

#n!을 구하는 재귀함수
def factorial(n):
    if n<=1:
        return 1
    else:
        return n*factorial(n-1)

 

 

 

#Recursive vs Iterative 예제 - 피보나치(Fibonacci) 순열

 

#Recursive 
def solution(n):
    '''
    F0 = 0
    F1 = 1
    Fn = Fn - 1 + Fn - 2, n >= 2
    '''
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else: 
        return solution(n-1)+solution(n-2)
        
solution(7) 
#[1]1 - [2]1 - [3]2 - [4]3 - [5]5 - [6]8 - "[7]13"
#[5]8 + [6]8 = "[7]13"
#Out: 13

solution(8) 
#[1]1 - [2]1 - [3]2 - [4]3 - [5]5 - [6]8 - [7]13 - "[8]21"
#[6]8 +[7]13 = "[8]21"
#Out: 21

 

#Iteratvie 
def solution(n):
    if n < 2:
        return n
    a, b = 0, 1
    for i in range(n): 
        a, b = b, a+b 
    return a
    
solution (4)
solution (8)
#[1]a,b=1,1 
#[2]a,b=1,2 
#[3]a,b=2,3 
#[4]a,b=3,5 
#[5]a,b=5,8
#[6]a,b=8,13
#[7]a,b=13,21
#[8]a,b=21,34
#a = 21
#Out: 21

#Recursive 예제 - 조합의 수 계산

#재귀적 방법으로 조합의 수 계산
#n개의 다른 원소에서 m개를 택하는 경우의 수
def combi(n, m):
    #if와 elif를 이용해 trivial case 
    if n == m:    #선택하는 원소의 개수가 전체 원소의 개수와 같으면 
        return 1 #1로 반환
    elif m == 0: #선택하는 원소 개수가 없으면 
        return 1 #1로 반환
    else: 
        return combi(n-1,m)+combi(n-1,m-1)

 

#Recursive 예제 - 이진탐색

#L은 리스트
#x는 찾으려는 원소
#l부터 u까지 리스트 내 범위 인덱스

def solution(L, x, l, u): 
    if l > u: 
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]: x가 mid보다 작을 경우
        return solution(L, x, l, mid-1) #mid의 오른쪽 날림
    else:
        return solution(L, x, mid+1, u) #mid의 왼쪽 날림