TIL99. Algorithm : Recursion 이해

📌 이 포스팅에서는 Python의 Recursion 개념과 예시에 대해 정리하였습니다.

🌈 Recursion 이해

🔥 Recursion 이란?

🔥 Recursion 예시

1. Recursion 이란?

🤔 재귀함수 개념

✔️ 재귀 함수란 어떤 함수에서 자기 자신을 다시 호출하여 반복적인 작업을 수행하는 방식의 함수를 의미한다.

✔️ 이에 재귀 함수는 반복문으로 변환할 수 있고, 반복문 또한 재귀함수로 변환할 수 있어야 한다.

✔️ 재귀 함수의 필수적인 조건은 종료 조건인데, 종료 조건이 없는 재귀함수는 'RecursionError'를 발생시키기 때문이다.

✔️ 이는 재귀 깊이에 대한 메모리 제한을 걸어두었기 때문이다.

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function() # RecursionError: maximum recursion depth exceeded while calling a Python object

🤔 재귀함수 특징

✔️ 재귀함수는 return으로 호출되는 함수를 stack 방식으로 계속 위로 쌓아올렸다가, 종료조건을 만나면 맨 위에서부터 하나씩 처리하는 방식으로 작동한다.

✔️ 여기서 스택 방식은 LIFO을 방식으로 작동하는 자료구조로 가장 마지막에 push한 데이터가 가장 먼저 pop 된다.

🤔 재귀 호출과 반복문 비교

✔️ 재귀 호출은 종료조건과 점화식만 있으면 구현 가능하기 때문에 가독성이 높지만, 재귀 호출의 제한이 존재하기 때문에 많은 호출이 필요할 때는 사용이 불가능 하다.

✔️ 또한 시간복잡도에 있어 재귀호출 구현과 반복문 구현은 차이가 없으나, 실제 Call Stack 과정에서 재귀호출이 속도가 느리고, 메모리를 크게 차지한다는 단점이 있다.

✔️ 이에 반해 반복문 구현은 전체 과정을 서술하기 때문에 코드의 길이가 비교적 길지만, 속도가 빠르고 호출의 제한이 없다는 장점을 가지고 있다.

✔️ 아래 1부터 N까지 수의 합을 구하는 공식으로 서로의 특징에 대해 살펴보도록 하겠다. 재귀식으로는 아래와 같이 해결할 수 있다.

✔️ 998까지는 가능하나, 999부터는 RecursionError 에러를 발생시킨다. 이처럼 재귀식으로 구현할 경우 호출의 제한이 발생한다.

import time
def sumN(n):
  if n == 1: return 1
  return sumN(n-1) + n
start = time.time_ns()
print(sumN(100)) # 5050
print('time :', time.time_ns()-start) # 110982
# print(sumN(998)) # 498501
# print(sumN(999)) # RecursionError: maximum recursion depth exceeded in comparison

✔️ 반복문으로 구현하면 아래와 같다. 코드의 가독성은 비교적 떨어지나 반복의 제한이 없다.

import time
def sumN(n):
    res = 1
    for i in range(2, n+1):
        res += i
    return res
start = time.time_ns()    
print(sumN(100)) # 5050
print('time :', time.time_ns()-start) # 44348
print(sumN(998)) # 498501
print(sumN(999)) # 499500
print(sumN(1000)) # 500500

✔️ N까지의 합을 구하는 공식으로는 가우스의 덧셈이라고 있다. 아래를 참조하길 바란다.

import time
def sumN(n):
  return n * (n + 1) // 2
start = time.time_ns()    
print(sumN(100)) # 5050
print('time :', time.time_ns()-start) # 32522

2. Recursion 예시

🤔 Factorial

✔️ input으로 N이 주어질 때, !N 값을 반환하는 문제다.

✔️ 참고로 수학적으로 0!, 1!는 모두 1이고, 시간복잡도는 O(N) 이다.

def factorial(n):
  if n <= 1: return 1
  return n * factorial(n-1)
print(factorial(5)) # 120

✔️ factorial 문제를 반복문으로 해결하면 아래와 같다. 조금 더 길다.

✔️ 시간복잡도는 for문이 1개기 때문에 이 또한 O(N)이다.

def factorial(n):
  res = 1
  for i in range(1, n+1):
    res *= i
  return res
print(factorial(5)) # 120

🤔 Fibonacci Number

✔️ Fibonacci Number는 피보나치 수열에서 N번째 피보나치수를 반환하는 문제다.

✔️ 여기서 N번째 Fibonacci 수란 N-1 수와 N-2수를 더한 값이다.

def fibonacci(n):
  if n <= 2: return 1
  return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(1)) # 1
print(fibonacci(2)) # 1
print(fibonacci(3)) # 2
print(fibonacci(4)) # 3
print(fibonacci(5)) # 5
print(fibonacci(6)) # 8
print(fibonacci(7)) # 13

✔️ for문으로 fibonacci 수열을 해결하면 아래와 같다. n-1, n-2 번째 수를 a,b에 저장해두고 해결할 수 있다.

def fibonacci(n):
  a, b = 1, 1
  if n==1 or n==2:
    return 1
  for i in range(1,n):
    a, b = b, a+b
  return a
print(fibonacci(1)) # 1
print(fibonacci(2)) # 1
print(fibonacci(3)) # 2
print(fibonacci(4)) # 3
print(fibonacci(5)) # 5
print(fibonacci(6)) # 8
print(fibonacci(7)) # 13