파이썬(Python) - 재귀 호출 / 스택(stack) / 유클리드 호제법

 

재귀 호출

• 자기 자신을 다시 호출하는 기능
• 함수 안에서 자신의 함수를 호출하는 기능
• 반복문 + stack 구조 (뒤로가기, undo, ctrl+z)

def sum(n):
      if n == 0:
          return 0
      return sum(n-1)+n # sum(n-1)에 대한 값은 모르니까 stack에 쌓아놓는다. 
sum(5)

돌아가는 방식(stack이 쌓이는 모습)

sum(1)          ----->   1

sum(1) + 2     -----> 1 + 2

ham(2) + 3     -----> 3 + 3

ham(3) + 4     -----> 6 + 4

ham(4) + 5     -----> 10 + 5  ===> 15

 

 

stack

• 한쪽 끝에서만 자료를 넣거나 뺄수있는 구조
• 바닥부터 데이터를 차곡차곡 쌓는 구조
• LIFO(Last In First Out) : 후입선출, 마지막으로 들어온 데이터가 제일 먼저 나간다.
• FILO(First In Last Out) : 선입후출, 처음에 들어온 데이터가 제일 마지막에 나간다.

stack 구조 용어

push : 마지막 데이터 위치에 데이터를 입력한다.

pop :  마지막 데이터 위치에 데이터를 꺼내는 작업(삭제)

top : 제일 최근에 들어간 데이터 즉 가장 위에 있는 데이터의 위치

 

push 함수 만들기 :

stack = []

def push(n) :

    global stack

    stack.append(n)

 

push(1)

push(2)

push(3)

stack

 

pop 함수 만들기 :    

def pop() :

     global stack

     if len(stack) == 0:

         return None

     return stack.pop()

 

pop()

stack

 

 

재귀 호출을 사용한 유클리드 호제법

유클리드 호제법

• 2개의 자연수로 최대공약수를 구하는 알고리즘
• 호제법 : 두 수가 상대방 수를 나누어 우너하는 수를 얻는 알고리즘

이미지 출처 : https://www.inchcalculator.com/euclidean-algorithm-calculator/

 

최대 공약수 구하기 (유클리드 호제법 X)

def gcd(x,y):
    # x, y의 약수 구하기
    a = []
    b = []
    for i in range(1, int(x/2)+1):
        if x % i == 0:
            a.append(i)
    a.append(x) # a = x의 약수들 
    for i in range(1, int(y/2)+1):
        if y % i == 0:
            b.append(i)
    b.append(y) # b = y의 약수들
    
    # a, b의 교집합 구하기
    c = []
    for i in a:
        if i in b:
            c.append(i)
    
    # c의 max값 구하기
    c.sort()
    return c[-1]

gcd(100,50)

 

최대 공약수 구하기 (유클리드 호제법 O)

def gcd(x,y):
    if x < y :    
        x,y = y,x  # x와 y 스위칭
    elif x > y :
        while y != 0:
            x = y
            y = x%y
    else :
        return x
    return x
gcd(100,50)

 

최대 공약수 구하기 (유클리드 호제법 O + 재귀 호출)

def gcd(x,y):
    if y == 0:
        return x
    return gcd(y, x%y)
gcd(100,50)

 

 

 

*최대공약수 구하기 코드 비교*

유클리드 호제법 X	유클리드 호제법 O	유클리드 호제법 O + 재귀 호출