TIL-29. [알고리즘] Recursion의 개념/팩토리얼/피보나치 수열

🤔 Recursion의 개념

재귀라는 뜻의 Recursion은 어떤 것을 정의할 때 자기자신을 재참조하는 걸 말하며
프로그래밍에서는 재귀함수 호출의 형태로 쓰인다.

관련 정보를 찾아보다가 인터넷에서 재귀를 설명하는 재미있는 예시를 보았다.

해당 글에서는 인형 안에 더 작은 인형이 들어가 있는 러시아의 마트료시카의 예를 들었는데,
너무 작아서 다른 인형을 더 이상 담지 못할 때까지 계속되는 이 인형의 특징처럼
어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써
바로 풀 수 있는 문제로 작아질 때까지 반복하는 테크닉을 재귀라고 설명하고 있었다.

재귀함수는 반복문의 무한루프와 비교 개념으로 소개되기도 하는데,
자기자신을 무수히 호출할 수 있지만 너무 작아 더 이상 담을 수 없는 마트료시카 인형처럼
결국엔 한계가 발생한다는 점에서 반복문의 무한루프와 차이점이 있다.

재귀함수는 호출될 때마다 메모리의 스택 영역에 차곡차곡 쌓이는데
종료 시점을 명시해 주지 않으면 결국 메모리 오버플로우가 발생되어 프로그램이 뻗게 된다.

위에 언급한 것처럼 스택 오버플로우의 문제 발생 가능성이 있고
시간복잡도가 반복문에 비해 계산이 어렵다는 단점이 있다.
또 메모리 사용량이 많기 때문에 수행 시간이 더 길어질 수도 있다.

하지만 어떠한 문제를 해결할 때 직관적인 가독성을 보여주고
트리 구조 등 특정 상황에서 유용하게 사용되는 개념이기에 꼭 알아두어야 한다.

아래는 이러한 재귀의 개념을 잘 보여주는 팩토리얼과 피보나치 수열 알고리즘 문제이다.

🤔 Factorial

from functools import reduce
a = []
def factorial(num):
  while num >= 1:
    a.append(num)
    num -= 1
 
  return reduce(lambda x, y: x * y, a)

print(factorial(3))

리스트를 만들고 reduce 모듈을 사용해서 팩토리얼을 구현해 보았다.
아래처럼 재귀의 형태를 이용해 구현할 수도 있다.

def factorial(num):
  if num <= 1: 
  	return 1
  return num * factorial(num-1)

print(factorial(3))

🤔 피보나치 수열

def fibonacci(num):
  if num == 1 or num == 2: 
  	return 1
  else: 
    return fibonacci(num-1) + fibonacci(num-2) 
print(fibonacci(4))

여러 가지 방법이 있는데 역시 재귀함수를 이용한 방법이다.