[알고리즘] 재귀

재귀(Recursion)

재귀란 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 말한다.

 

재귀를 사용하면 특정 프로그램을 간결하고 효율성 좋게 작성할 수 있다.

 

가장 대표적인 예시로 팩토리얼(Factorial)이 있다. 

팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 "순차 곱셈"이라고도 한다.

 

ex. 0! = 1, 2! = 1 x 2 = 2

 

팩토리얼은 일정한 공식 있는데, 10!은 10 x 9!과 같이 나타낼 수 있다.

이를 일반화하면 n! = n x (n-1) x .... x 1와 같이 나타 낼 수 있다.

 

이 공식를 사용하여 팩토리얼을 구하는 재귀 함수와 일반 함수를 작성해서 비교해보자.

# 일반함수로 팩토리얼 구현
def factorial(n:int)->int:
    sum = 1
    for i in range(2,n+1):
        sum *= i
    return sum

# 재귀함수로 팩토리얼 구현
def factorial(n:int):
    if n == 1:
        return n
    else :
        return n * factorial(n-1)

# 파이썬 내장 라이브러리 math를 사용한 팩토리얼 구현
from math import factorial
print(factorial(7))

파이썬은 math 라이브러리에 factorial 메소드를 구현해 놓았기 때문에 따로 구현하지 않아도 사용가능하다.

 

 

직접 재귀와 간접 재귀

직접 재귀 : 자신과 똑같은 함수를 호출하는 방식

간접 재귀 : a(), b() 함수가 있다고 했을 때 a에서 b를 호출하면 b가 a를 호출하는 방식

 

유클리드 호제법

유클리드 호제법은 두 정숫값의 최대 공약수(GCD)를 구하는 방법이다.

두 수를 나누었을 때 나머지를 계속해서 구하고, 나머지가 0이 되는 순간의 나누는 수가 두 수의 최대 공약수가 된다.

 

과정

1. 입력 받은 두 수를 'a', 'b'라고 가정한다.
2. 'b'가 0이 될 때까지 다음의 과정을 반복한다.
   • 'a'를 'b'로 나눈 나머지를 구한다.
   • 'a'에는 'b'를 대입하고, 'b'에는 나머지를 대입한다.
3. 'b'가 0이되었을 때, 'a'가 두 수의 최대공약수가 된다.

 

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

def gcd(a:int,b:int)->int:
	while b!=0:
    	a,b = b, a%b
    return a

재귀 방법으로도 구현할 수 있다.

# 재귀를 사용한 구현
def gcd(a:int,b:int)->int:
    if b==0:
        return a
    else:
        return gcd(b,a%b)
print(gcd(48, 18))

math의 gcd() 메소드를 사용할 수도 있다.

# math의 gcd() 메소드
from math import gcd
print(gcd(48,18))

 

 

하양식 분석과 상향식 분석

하양식 분석(top-down)

• 가장 위쪽에 위치한 함수 호출부터 시작하여 계단식으로 내려오면서 조사하는 방법 
• 같은 함수를 여러번 호출할 수 있는 단점이 존재함

상향식 분석(bottom-up)

• 아래쪽 부터 쌓아 올리면서 조사하는 방법

 

 

하노이의 탑(Towers of Hanoi)

작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해 n개의 원반을 옮기는 문제

 

규칙

1. 세 개의 기둥(A,B,C)이 주어진다.
2. 기둥 A에는 크기가 다양한 원반이 쌓여 있고 B,C는 비어 있다.
3. 원반들은 크기에 따라 다르며, 작은 원반이 큰 원반 위에 쌓일 수 없다.
4. 모든 원반들은 기둥 A -> C로 옮겨야 한다.
5. 한 번에 하나의 원반만 옮길 수 있으며, 옮기는 과정에서 다른 기둥에 작은 원반이 큰 원반 위에 올라가지 말아야한다.

 

 과정

1. n-1개의 원반을 B 기둥으로 옮긴다.
2. 나머지 가장 큰 원반을 A->C로 옮긴다.
3. 나머지 원반들을 C로 옮긴다.

 

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

def hanoi(n:int, from_:str, to_:str, via_:str)->None:
    # from_ : 출발지 기둥
    # to_ : 목적지 기둥
    # via_ : 보조 기둥
    if n == 1:
        print(from_, "->", to_)
    else:
        hanoi(n-1, from_, via_, to_)
        print(from_, "->", to_)
        hanoi(n-1, via_, to_, from_)
print("출발 -> 목적")
hanoi(3,'A','C','B')

 

코드 모음

재귀.ipynb