[알고리즘] 재귀함수 - 최대공약수, 피보나치 수열

* <모두의 알고리즘 with 파이썬>의 문제 05를 정리한 내용입니다.

 

 

1. 일반적인 알고리즘으로 최대 공약수 구하기 

# 최대공약수 알고리즘 
def gcd_algorithm (a, b):   
    i = min(a,b)
    while True: 
        if a%i == 0 and b%i == 0 :
            print("GCD = {}".format(i))
            return i 
        i = i-1 
        print("i = {} " .format(i))

• 두 개의 숫자를 입력받는다. 
• 입력받은 수 중 작은 수를 찾는다. (min (a,b)) 생각해보면 당연한 프로세스다. 최대 공약수라는 말 자체가 입력 받은 두 개의 수를 나누는 수 중 공통인 것들 중, 가장 큰 것인데 -- 어떤 수를 나누려면 그 수보다 커서는 안된다 (되긴 하는데 여기서는 안됨, 분수 X) 
• if문에 걸려 값을 return 하기 전까지 다음을 반복 
  • if문 조건: 두 수를 나눴을 때 나머지가 모두 0인 수
  • 아니라면 두 수 중 작은 수에서 계속해서 1을 빼주고 위의 if문을 시도한다 

 

 

2. 재귀함수로 최대공약수 구하기 

# 재귀 함수로 최대공약수 알고리즘 
def recursive_gcd(a, b):
    print("gcd: ", a, b)
    if b == 0:
        return a
    print("a%b: {} \n".format(a%b))
    return recursive_gcd(b, a%b)

• 저번 포스팅을 작성할 때 재귀함수를 완벽히 이해했다고 생각했는데, 변형 문제를 막상 풀려니 적용 못하겠더라... 아직 더 익숙해질 필요가 있는듯 ㅠㅠ
• 위와 마찬가지로 숫자 2개를 입력으로 받는다. 
• 종료 조건은 오른쪽에 입력받는 숫자 (처음에는 그냥 숫자, 이후부터는 나머지)가 0일 때이다. 종료시 반환 값은 왼 쪽에 있는 숫자이며, 최대공약수이다. 
•  재귀함수의 입력값은 초기에 입력 받았던 b와 a를 b로 나누고 남은 나머지이다. 

 

 

3. 재귀함수로 피보나치 수열 구하기 

def fibonacci(n, m, ls):
    # n: 선행
    # m: 후행
    t = n + m
    
    if len(ls) == 0: 
        ls.append(n)
        ls.append(m)
        ls.append(t)
    else: 
        ls.append(t)
     
    print(ls)
    if len(ls) == 7: 
        return (n+m)
    
    return fibonacci(m, t, ls)

• 마지막 문제는 7번째 피보나치 수열을 재귀함수로 푸는 문제였다. 
• 피보나치 수열의 첫 번째 숫자, 두 번째 숫자, 빈 list를 입력으로 준다. 
• 만약에 첫 번째 숫자 (n)이 0이면 n, m, t (n+m)을 list에 추가하여 초기 세팅을 완료해주고, 첫 번째 숫자가 0이 아니라면 t만 추가해준다. 
• 종료 조건은 이렇게 피보나치 숫자가 추가된 리스트의 길이가 (우리가 구하고자 하는) 7이 된다면 종료한다.