[알고리즘] 3. 재귀 호출

1. 팩토리얼 구하기

팩토리얼 알고리즘 : 1부터 n까지 연속한 정수의 곱 구하기

1) 팩토리얼 알고리즘 (재귀없이)

#1부터 n까지 곱하기
def fact(n):
    f = 1
    for i in range(1,n+1):
        f = f*i
    return f
 
print(fact(10))

2) 팩토리얼 알고리즘 (재귀)

재귀 호출 : 어떤 함수 안에서 자기 자신을 부르는 것

#1부터 n까지 곱하기
def fact(n):
    if n <=1: #종료조건
        return 1 
    return n*fact(n-1)
 
print(fact(10))

3) 알고리즘 분석

시간복잡도 = O(n)

 

2. 최대공약수 구하기

최대공약수 : 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값

1) 최대공약수 알고리즘

def gcd(a,b):
    i = min(a,b)
    while True:
        if a % i ==0 and b%i==0:
            return i
        i = i-1
 
    
print(gcd(3,6))
 

 

2) 유클리드 알고리즘

유클리드 최대공약수 : 1. a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다.

                                     -> gcd(a,b)=gcd(b,a%b)

                             2. 어떤 수와 0의 최대공약수는 자기자신이다.  -> gcd(n,0)=n

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
 
    
print(gcd(3,6))
 

3. 하노이의 탑 옮기기

1) 하노이의 탑 알고리즘 

하노이의 탑 알고리즘 : 원반이 n개일 때 n-1개를 다른 기둥에 옮기는 것이 포인트! 

# n = 옮기려는 원반의 개수
# from_pos = 옮길 원반이 현재 있는 출발점 기둥
# to_pos = 원반을 옮길 도착점 기둥
# aux_pos =  보조 기둥
def hanoi(n,from_pos, to_pos, aux_pos): 
    if n==1:
        print(from_pos, "->", to_pos)
        return
    
    hanoi(n-1, from_pos,aux_pos,to_pos) #n-1개의 원반을 보조기둥으로
    print(from_pos,"->",to_pos)
    hanoi(n-1,aux_pos,to_pos,from_pos) #n-1개의 원반을 도착점 기둥으로
 
print("n=1")
hanoi(2,1,3,2)
 
 

2) 알고리즘 분석

시간복잡도 = O(2^n)

 

---

연습문제

4-1. 

def sum(n):
    if n <=1:
        return 1
    return n+sum(n-1)
 
print(sum(10))

4-2.

#처음에는 a[0]를 max로
#그뒤로 a[1],a[2]....비교하기
def find_max(a,n):
    if n ==1:
        return a[0]        #max값 첫번째 값으로
    max = find_max(a,n-1)
    if max > a[n-1]:
        return max
    else:
        return a[n-1]
 
 
a=[12,13,14,15,2]
print(find_max(a,5))

5-1.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-2) + fibonacci(n-1)
 
    
print(fibonacci(5))