<알고리즘> 재귀 알고리즘 (1)

 

1. 재귀 알고리즘의 기본

* 재귀란

 - 재귀 : 어떤 사건에서 자기 자신을 포함하고 다시 자신을 사용하여 정의되는 것.

 

* 팩토리얼 구현

 - n! 정의

 

  ① 0! = 1

  ② n > 0 이면 n! = n x (n-1)!

 

 이 경우 n이 0이 아닌 수일 경우 ②를 실행하고 이는 또 다시 그 보다 1작은 수의 ②를 시행함을 알 수 있다.

 

def factorial(n: int) -> int :
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1

x = int(input())
print(factorial(x))

# 5
# 120

 : 매개 변수 5를 먼저 받고, 5 * factorial(4)을 계산해야한다. 이 때 이 곱셈을 위해 factorial(4)를 호출한다.

 차례로 factorial(3), factorial(2), factorial(1)을 실행하고 n이 0일 때 처음으로 return문이 실행되어 1을 내보낸다.

 

 1을 전달받은 함수는 factorial(1)=1 x 1 을 내보낸다. 그리고 마침내 factorial(2)=2 * 1 이 실행될 것이다. 그 후 factorial(3) = 3 * 2 가 실행된다. 차례로 반환되어 마지막으로 return 5 * 24 가 반환되어 120이 출력된다.

 

 - 재귀호출 : 위와 같이 값을 구하기 위해 자기 자신과 같은 함수를 호출하는 행위

 

 - 직접재귀 : 위와 같이 f함수가 자신과 같은 f함수를 호출하는 것

 

 - 간접재귀 : f함수가 g함수를 호출하고, g함수가 다시 f함수를 호출하는 구조

 

* 유클리드 호제법

 - 유클리드 호제법은 최대공약수(GCD)를 재귀적으로 구하는 방법이다.

 - 두 정수의 최대공약수를 구하는 문제는 다음과 같이 생각할 수도 있다.

 

Q. 두 정수를 각각 변으로 가진 직사각형이 있다. 이 때 정수의 변을 가진 정사각형을 최소한으로 사용하여 채워나갈 때, 가장 작은 정사각형의 변은 얼마인가?

 

A. 최소한의 정사각형을 사용하기위해 사용가능한 최대크기의 변을 사용한다. 먼저 작은 쪽 변의 크기인 6을 사용하여 정사각형을 채운다.

  그리고 나머지도 마찬가지로 작은 쪽 변의 크기인 2를 사용하여 정사각형을 채운다. 따라서 답은 2 (GCD)

 

 - 위 과정을 gcd(x,y) 라는 함수로 나타내면 다음과 같다.

 

  ① y = 0 이면 x

  ② y ≠ 0 이면 gcd(y, x % y )

 

 - 이를 코드로 구현하면 다음과 같다.

 

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

a = int(input())
b = int(input())
print(gcd(a,b))

# 6
# 14
# 2

 

2. 재귀 알고리즘 분석

* 순수한 재귀

 - 앞서 다룬 함수들과 달리 함수 안에서 재귀호출을 여러번 실행하는 함수

def recur(n) :
    if n > 0 :
        recur(n - 1)
        print(n)
        recur(n - 2)

x = int(input('입력 : '))
recur(x)

# 입력 : 3
# 1
# 2
# 3
# 1

 

* 하향식 분석

 - 매개변수에 3을 전달하면 위 함수는 다음 순서를 따른다.

 

  ① recur(2)

  ② 3 출력

  ③ recur(1)

 

 - 이를 아래로 뻗어나가는 가지형식으로 그려보면 다음과 같다.

 

 - 위와 같이 하향식 분석된 것을 살펴보면 왼쪽 화살표를 따라 계속 내려가며, 더 이상 없을 때 올라오며 차례로 출력한다.

 - 위에서 recur(1)을 여러번 호출하고 있으므로 이 분석은 효율적이지만은 않다.

 

* 상향식 분석

 - 하향식 분석과는 반대로 아래에서부터 쌓는 방식이다.

 - 위 함수는 양수일 때만 실행되므로 recur(1) 부터 알아볼 수 있다.

 

 - 위와 같이 recur(1)부터 알아보며 recur(3)까지 알아낼 수 있다.

 

 

 

 

---

 

참고

 

 

 

 

 

이 글은 ‘이지스퍼블리싱’의 ‘자료구조와 함께 배우는 알고리즘 입문’을 공부 후 정리하며 쓴 글입니다.

작성된 모든 내용과 코드는 교재 및 관련 사이트를 참고하여 직접 재구성하였습니다.

 

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

http://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

이지스퍼블리싱 스터디룸 카페

Do it! 스터디룸 : 네이버 카페

 

교재 공식 깃허브

easysIT/doit_dsalgo_with_python

위키백과

유클리드 호제법 - 위키백과, 우리 모두의 백과사전