재귀 알고리즘

출처: Do it! 자료구조와 함께 배우는 알고리즘 입문

재귀 알고리즘의 개념

팩토리얼 n!

팩토리얼 n! 정의(n은 양의 정수)

0! = 1

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

def factorial(n:int) -> int:
  #양의 정수 n 팩토리얼값을 재귀적으로 구함
  if n>0:
    return n* factorial(n-1)
  else:
    return 1

if __name__ == '__main__':
  n = int(input('출력할 팩토리얼값을 입력하세요: '))
  print(f'{n}의 팩토리얼은 {factorial(n)} 입니다. ')

출력할 팩토리얼값을 입력하세요: 4

4의 팩토리얼은 24 입니다.

 

factorial함수의 기전은 다음과 같다.

factorial() 함수로 3!값을 구한다면,

1)n=3을 받아 3*factorial(2) 값을 반환하고, n-1의 값이었던 2를 다시 n에 받는다 즉, (3*2)

2)n=2를 받아 2*factorial(1) 값 반환, 1의 값을 n에 받음. 즉(2*1)

3)n=1을 받아 1*factorial(0) 값 반환 , 즉(1*1) 

이렇게 해서 3!값이 6을 얻을 수 있다. 이러한 함수 호출을 재귀호출이라고 한다.

 

직접 재귀와 간접 재귀

factorial 함수는 자신과 똑같은 함수를 호출하는데, 이와 같은 방식을 직접(direct) 재귀라고 한다.

이와 다르게 간접(indirect) 재귀는 a->b->a 이런식으로 다른함수를 통해 자신을 호출한다.

 

유클리드 호제법

두 정수의 최대공약수를 구한다. x,y의 최대 공약수를 gcd(x,y)로 표기한다. 예를 들어 x= az, y= az를 만족하는 정수 a,b와 최대의 정수 z가 존재할 때, z는 gcd(x,y)라고 할 수 있다. 최대공약수는 다음과 같이 구한다.

1) y가 0이면 .. x

2) y가 0이 아니면 ... gcd(y, x%y)

def gcd(x:int,y:int)->int:
  #정수값 x와 y의 최대 공약수를 반환
  if y==0:
    return x
  else:
    return gcd(y,x%y)

if __name__ =='__main__':
  print('두 정숫값의 최대 공약수를 구합니다.')
  x= int(input("첫번쨰 정숫값을 입력하세요: "))
  y= int(input("두번째 정숫값을 입력하세요: "))
  print(f'두 정숫값의 최대 공약수는 {gcd(x,y)} 입니다. ')

두 정숫값의 최대 공약수를 구합니다.

첫번쨰 정숫값을 입력하세요: 22

두번쨰 정숫값을 입력하세요: 30

두 정숫값의 최대 공약수는 2 입니다

 

재귀 알고리즘 분석

def recur(n:int)-> int:
  #순수한 재귀함수 recur 구현
  if n>0:
    recur(n-1)
    print(n)
    recur(n-2)

x = int(input('정수값을 입력하세요: '))
recur(x)

하향식 분석

recur(4) 실행과정 : 1) recur(3), print(4), recur(2)

직접 그림 허접 주의,,

전달받은 값이 0 이하면 recur() 함수는 상자에 -를 표시하면 비어있다는 의미이다. 화살표를 따라 한칸 아래쪽 상자로 이동하고, 다시 원래 호출한 상자로 돌아오면 네모 박스안의 값을 출력한다. recur값이 0이하일 경우에는 빈박스(-)를 표시한다. 이런식으로 가장 위쪽에 위치한 상자의 함수 호출에서 시작하여 계단식으로 자세히 조사해 나가는 분석을 하향식 분석이라고 한다. 꼭대기부터 하면 여러번 호출하게 됨으로 효율적인 분석이라고 할 수는 없다.

 

상향식 분석

상향식 분석은 하향식과 반대로 아래쪽부터 쌓아서 분석한다. recur(1)부터 실행하면 다음과 같다.

1) recur(0) 2) 1출력 3)recur(-1)

recur(0)과 recur(-1)은 출력할 내용이 없으므로 1만 출력된다. 

 

다음으로 recur(2)를 보면

1) recur(1) 2) 2출력 3)recur(0)

recur(1)은 1을 출력하고, recur(0)은 아무것도 출력하지 않아 1,2를 출력한다. 

 

recur(4)의 최종출력 상향식 구조는 다음과 같다.

------------------

recur(-1): 아무것도 x

recur(0): 아무것도 x

============

recur(1) : recur(0) 1 recur(-1) -> 1

recur(2) : recur(1) 2 recur(0) -> 1 2

recur(3) : recur(2) 3 recur(1) -> 1 2 3 1

recur(4) : recur(3) 4 recur(2) -> 1 2 3 1 4 1 2 

 

recur(4)를 보면 1231은 recur(3)의 출력, 4, 12는 recur(2)의 출력이다.

비재귀적 표현

꼬리 재귀 제거

n의 값을 n-2로 업데이트하고 함수의 시작 지점으로 돌아감

def recur(n:int)-> int:
  #꼬리 재귀 제거 recur 구현
  if n>0:
    recur(n-1)
    print(n)
    n = n-2

x = int(input('정수값을 입력하세요: '))
recur(x)

재귀를 제거하기

스택을 이용하여 비재귀적으로 구현한다.

from stack import Stack

def recur(n:int)-> int:
  #재귀를 제거한 recur 함수
  s= Stack(n)
  while True:
    if n >0:
      s.push(n)
      n = n-1
      continue
    if not s.is_empty(): #스택이 비어있지 않아면
      n= s.pop() #저장한값을 n에 팝
      print(n)
      n= n-2
      continue
    break

x= int(input('정수값 입력:'))
recur(x)

사진 개허접,, ㅈㅅ

pop한 값의 n-2를 했을때 양수면 첫번째 if문 발동, 음수면 아래의 if문 발동하고 아무것도 없고 n=0 이기 때문에 break를 건다.