๐ ์ด ํฌ์คํ ์์๋ Python์ Recursion ๊ฐ๋ ๊ณผ ์์์ ๋ํด ์ ๋ฆฌํ์์ต๋๋ค.
๐ฅ Recursion ์ด๋?
๐ฅ 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
โ๏ธ 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๋ ํผ๋ณด๋์น ์์ด์์ 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
์ฒ์ฌ์ธ๊ฐ์.....?