재귀 알고리즘

🤔들어가면서🤔

파이썬 다 까먹었다;

💻 파이썬 함수 선언 방법

📌 재귀

재귀 알고리즘이란

자기 자신으로 돌아간다는 의미, 중복되고 반복되는 부분을 나누고 각 부분의 문제를 해결한 후 결과를 조합해 문제의 답을 찾는 방법이다.

재귀 알고리즘의 법칙

• 종료조건을 가진다.
• 자기 자신의 상태를 변경하면서 종료 조건에 가까워진다.
• 반드시 자기 자신으로 다시 돌아와 호출한다.

대부분의 반복 알고리즘은 재귀 알고리즘으로 해결할 수 있다.

반복 알고리즘

동일한 루프로 단계를 반복해 문제를 해결하는 알고리즘을 말한다.

🙆 장점

• 코드문이 간결해진다.

🙅‍ 단점

• 내부 스택을 이용하므로 더 많은 메모리를 사용한다.

💻 코드로 알아보기

반복 알고리즘을 이용한 팩토리얼

def factorial_1(n):
  the_product = 1
  while n > 0:
    the_product *= n 
    n -= 1
  return the_product

재귀 알고리즘을 이용한 팩토리얼

def factorial_2(n):
  the_product = 1
  if n == 0:
    return 1
  return n * factorial_2(n-1) 

print(str(factorial_2(3))) 

➡️ 6 출력

🤔 중간 결과는 어디에 저장될까?: 재귀의 내부 스택 사용

반환값을 스택에 잠시 담는다. (이후 자료구조에서 더 공부할 것)

n이 3일때의 내부 스택

  return n * factorial_2(n-1)   # n = 3
  return n * factorial_2(n-1)   # n = 2
  return n * factorial_2(n-1)   # n = 1
  1                             # factorial_2(0) = 1

  return n * factorial_2(n-1)   # n = 3
  return n * factorial_2(n-1)   # n = 2
  1

  return n * factorial_2(n-1)   # n = 3
  2 

  6  

return 6