재귀 알고리즘

재귀란

어떠한 이벤트에서 자기 자심을 포함하고 다시 자기자신을 사용하는 경우

팩토리얼

0! = 1

n>0 이면 n! = n * (n-1)!

직접 재귀와 간접 재귀

• 직접재귀는 자신과 똑같은 함수를 호출하는 방식
• 간접재귀는 a() 함수가 b()함수를 호출하고 다시 b()함수가 a()함수를 호출하는 구조

유클리드 호제법

• 최대 공약수 구하는 방법
• 두 정숫값이 주어질 때 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 최대 공약수
• 나누어 떨어지지 않으면 작은 값과 나머지에 대해 재귀적으로 반복

하향식 / 상향식 분석

• 하향식 분석은 가장 위쪽에 위치한 상자의 함수 호출 부터 계단식으로 자세히 분석해가는 방법
• 상향식 분석은 아래쪽부터 쌓아 올리며 분석하는 방법

재귀 알고리즘의 비재귀적 표현

1. 꼬리 재귀 제거

   def recur(n: int) -> int:
   	while n> 0:
   		recur(n-1)
   		print(n)
   		n = n-2

2. 재귀 제거

   • n값을 임시로 저장해야한다 recur(n-1)의 처리를 하고 n 값을 출력할 때 임시로 저장한 값을 출력해야함 → stack으로 해결 가능

   from stack import Stack
   
   def recur(n:int) -> int:
   	s = Stack(n)
   	while True:
   		if n>0 :
   			s.push(n) # n값을 push 
   			n = n-1
   			continue
   		if not s.is_empty(): # stack이 비어있지 않으면
   			n = s.pop() # 저장한 값을 n에 팝
   			print(n)
   			n = n-2
   			continue
   		break
   
   x = int(input('정숫값을 입력하세요.'))
   
   recur(x)