Recursion

Python Algorithm Study - Week 5, 6

Algorithmpython

2017-08-17


Problem Solving with Algorithms and Data Structures using Python ์ฑ…์„ ์ฝ์œผ๋ฉฐ ์Šคํ„ฐ๋””ํ•œ ๋‚ด์šฉ์„ ์ •๋ฆฌํ•˜์—ฌ ์—ฐ์žฌํ•ฉ๋‹ˆ๋‹ค.


1. Recursion ์ด๋ž€?

  • Breaking down a problem into smaller and easier subproblems
  • A recursive function is a function that calls itself
  • Itโ€™s ELEGANT!

Recursion์ด๋ž€ ๋ฌธ์ œ๋ฅผ ๊ฐ€์žฅ ์ž‘์€ ๋‹จ์œ„๊นŒ์ง€ ์ชผ๊ฐœ์„œ ํ•ด๊ฒฐํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ํ•จ์ˆ˜๋ฅผ ๋ฐ˜๋ณตํ•ด์„œ ํ˜ธ์ถœํ•˜๋ฉฐ ๊ฐ€์žฅ ์ž‘์€ ๋‹จ์œ„๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€๊ธฐ๋งŒ ํ•ด๋„ ํฐ ๋‹จ์œ„์˜ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ์•„๋ž˜๋Š” ๋ฆฌ์ŠคํŠธ์˜ ๋ชจ๋“  ๊ฐ’์„ ๋”ํ•˜๋Š” recursiveํ•œ ํ•จ์ˆ˜์ด๋‹ค.

# Recursive sum
list = [2, 4, 6, 8, 10]

def recursive_sum(list):
    if len(list) == 1:  # base-case
        sum = list[0]
        return sum
    else:
        sum = list[0] + recursive_sum(list[1:])
        return sum

์—ฌ๊ธฐ์„œ len(list) == 1 ์ธ ๊ฒฝ์šฐ๋ฅผ ์ •์˜ํ•˜๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ์ค‘์š”ํ•œ๋ฐ, ์ด๋ฅผ base case ๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. Recursion์—์„œ๋Š” base case๋ฅผ ์ž˜ ์ •์˜ํ•˜๋Š” ๊ฒƒ์ด ์ œ์ผ ์ค‘์š”ํ•˜๋‹ค. ๋ฐ˜๋ณตํ•ด์„œ ๋Œ์•„๊ฐ€๋Š” recursive function์ด ์ข…๋ฃŒ๋˜๋Š” ์กฐ๊ฑด์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๊ฐ€์žฅ ์ž‘์€ recursive function ์„ ์ •์˜ํ•˜๋ฉด ๋‚˜๋จธ์ง€๋Š” ๊ทธ๋ƒฅ ํ•จ์ˆ˜๋ฅผ recursiveํ•˜๊ฒŒ ๋ถˆ๋Ÿฌ์˜ค๊ธฐ๋งŒ ํ•˜๋ฉด ๋œ๋‹ค.


2. 3 laws of recursion

  1. must have a base case
  2. state-changing & move toward the base case
  3. must call itself, recursively
# Recursive factorial
def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n-1)

์—ฌ๊ธฐ์„œ base case๋Š” n์ด 1๋ณด๋‹ค ์ž‘์„ ๋•Œ์ด๋‹ค. 1๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ์—๋Š” ์ž๊ธฐ ์ž์‹ ์„ ๊ณ„์† ๋ถˆ๋Ÿฌ์˜ค๋ฉฐ base case๋ฅผ ํ–ฅํ•ด ์ƒํƒœ๋ฅผ ๋ณ€๊ฒฝํ•œ๋‹ค.

  • 10์ง„๋ฒ• ์ˆ˜๋ฅผ (2~16)์ง„๋ฒ• ์ˆ˜๋กœ ๋ณ€ํ™˜ํ•ด๋ณด์ž!
# % ๋Š” ๋‚˜๋จธ์ง€, // ๋Š” ๋ชซ
def toStr(n, base):
    convertString = "0123456789ABCDEF"
    if n < base:
        return convertString[n]
    else:
        return toStr(n // base, base) + convertString[n % base]
  • Readability over Time complexity : Recursion๋Š” for๋ฌธ์„ ๋Œ๋ฆด ๋•Œ๋ณด๋‹ค time complexity๊ฐ€ ๋†’๋‹ค. ์ž๊ธฐ ์ž์‹ ์„ ๊ณ„์† ๋ถˆ๋Ÿฌ์˜ค๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰๋„ ํฌ๋‹ค. (for๋ฌธ์˜ ๊ฒฝ์šฐ ๊ฐ’์„ ๊ตฌํ•˜๊ณ  ๋ฐ”๋กœ๋ฐ”๋กœ ๋ฐ˜ํ™˜ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ผ์ •ํ•œ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.) ๊ทธ๋Ÿฌ๋‚˜ ์ฝ๊ธฐ ์ข‹์€ ์ฝ”๋“œ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

3. Binary Search

์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ์—์„œ ํŠน์ • ๊ฐ’์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•. ํฐ ๊ฐ’(high)๊ณผ ์ž‘์€ ๊ฐ’(low)์ด ์žˆ๊ณ  ์ค‘๊ฐ„๊ฐ’(mid)์ด ๊ทธ ์‚ฌ์ด์— ์žˆ๋Š”์ง€ ๋ณด๋ฉด์„œ ํ•ด๋‹น ๊ฐ’์˜ ์œ„์น˜๋ฅผ ์ฐพ๋Š”๋‹ค.

def binary_search(data, target, low, high):
    if low > high:
        return False    
    else:
        mid = (low + high) // 2
        if target == data[mid]:     
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid-1)
        else:   
            return binary_search(data, target, mid+1, high)

4. Visualizing Recursion

  • Fractal

    • The fractal has the same basic shape no matter how much you magnify it
  • Python์˜ visualizing ํˆด์ธ turtle์„ ์‚ฌ์šฉํ•˜๋ฉด ๋‹ค์–‘ํ•œ fractal์„ ์‹œ๊ฐํ™” ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ํ•จ๊ป˜ ๋ณด๊ธฐ ๐Ÿ‘‰ ํ•˜๋…ธ์ด์˜ ํƒ‘ ๋ฌธ์ œ - n๊ฐœ ๋†’์ด์˜ ํ•˜๋…ธ์ด ํƒ‘์ด ์žˆ๋‹ค๊ณ  ํ•˜์ž. ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์ฒซ๋ฒˆ์งธ ๋””์Šคํฌ ๋‹ค๋ฅธ ๊ณณ์œผ๋กœ ์˜ฎ๊ธฐ๋ฉด, ๋‚จ์€ (n-1)๊ฐœ ํƒ‘์— ๋Œ€ํ•œ ํ•˜๋…ธ์ด ํƒ‘์ด ๋œ๋‹ค. ๊ทธ๋ž˜์„œ ํ•˜๋…ธ์ด์˜ ํƒ‘๋„ ์žฌ๊ท€๋ฅผ ์ด์šฉํ•ด์„œ ํ’€ ์ˆ˜ ์žˆ๋‹ค.
  • ํ•จ๊ป˜ ๋ณด๊ธฐ ๐Ÿ‘‰ Memoization - ์ด๋ฏธ ๊ตฌํ•œ ๊ฐ’์€ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅํ•˜๊ณ  ๋‹ค์‹œ ๊ตฌํ•˜์ง€ ์•Š๋„๋ก ํ•˜์—ฌ ๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ์—ฐ์‚ฐํ•˜๋Š” ๋ฐฉ๋ฒ• (Mincoins)