TIL99. Algorithm : Recursion ์ดํ•ด

ID์งฑ์žฌยท2021๋…„ 12์›” 13์ผ
1

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
18/20
post-thumbnail

๐Ÿ“Œ ์ด ํฌ์ŠคํŒ…์—์„œ๋Š” 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
profile
Keep Going, Keep Coding!

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2021๋…„ 12์›” 21์ผ

์ฒœ์žฌ์ธ๊ฐ€์š”.....?

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ