5장 재귀 알고리즘

재귀란?

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

특징 : 스택처럼 마지막에 들어간 것이 첫번째로 종료가 된다.

장점 : 재귀를 사용하면 코드가 간결해진다.!!!

단점 : 너무 깊이 들어가면 오류가 날 수도 있다.

처리할게 많아지면 구조가 많이 복잡해진다.

1) 팩토리얼

def fact(n):
    if n > 0:
        return n * fact(n - 1)
    else
        return 1
fact(5)

순서

fact(5) = 5 * fact(4) ==> fact(4)로 진입
fact(4) = 4 * fact(3) ==> fact(3)로 진입
fact(3) = 3 * fact(2) ==> fact(2)로 진입
fact(2) = 2 * 1 ==> 종료 2 리턴
fact(3) = 3 * 2 종료 6 리턴
fact(4) = 4 * 6 종료 24 리턴
fact(5) = 5 * 24 종료 120 리턴
최종리턴 120

2) 유클리드 호제법

두 정수의 최대 공약수(GCD)를 구하는 방법 중 재귀를 이용함

x = az, y = bz를 만족하는 정수 a,b와 최대의 정수 z가 존재할 때 z는 gdc(x, y)이다.

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

3) 하노이 탑

총 3개의 기둥이 존재함. 첫번째 기둥에 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 가진 원반들을 세번째 원반으로 모두 옮기기

def move(no, x, y):
    if no > 1:
        move(no - 1, x, 6 - x - y)
    if no > 1:
        move(no - 1, 6 - x - y, y)
move(3, 1, 3)# 원반, 첫번째 기둥, 세번째 기둥

4) 8퀸문제

8개의 퀸이 서로 공격하여 잡을 수 없도록 8 * 8 체스판에 배치하라

모든 경우의 수 : 178,462,987,637,760

모두 배치 후 조건을 확인하면 경우의 수가 너무 많아 확인하는데 매우 많은 시간이 걸린다.

1) 각 열에 퀸을 하나만 배치한다.
2) 각 행에 퀸을 하나만 배치한다.
3) 현재 위치에서 대각선에 다른 퀸이 없으면 최종 배치를 한다.

이러한 분기처리를 하면 실행시간을 줄일 수 있다.

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