Recursion

 

 

# Recursion - my version

def split_str(s):

# Base Case

if len(s) == 0: 

return

print(s[:1])

return split_str(s[1:])

 

split_str('hello')

 

# 결과

h

e

l

l

o

 

 

# Recursion Sum

def recur_sum(n):

# Base Case

if n == 0:

return 0

else:

return n + recur_sum(n - 1)

 

print(recur_sum(4))

 

# 결과

10

 

# Recursion Sum 2

def recur_sum2(n):

if len(str(n)) == 1:

return n

else:

return n % 10 + recur_sum2(n // 10)

 

print(recur_sum2(4321))

 

print("4321 % 10 = {}".format(4321 % 10))

print("4321 // 10 = {}".format(4321 // 10))

 

# 결과

10

4321 % 10 = 1

4321 // 10 = 432

 

 

# Recursion - string split

def word_split(phrase, words, output = None):

 

if output is None:

output = []

 

for word in words:

if phrase.startswith(word):

output.append(word)

return word_split(phrase[len(word):], words, output)

 

return output

 

o = word_split('manranthe', ['clown', 'ran', 'man'])

print(o)

 

# 결과

['man', 'ran']

 

 

# Reverse a String

def reverse(s):

#Base Case

if len(s) <= 1:

return s

 

return reverse(s[1:]) + s[0]

 

o = reverse('hello')

print(o)

 

# 결과

olleh

 

 

# String Permutation

 

""" 중요한 로직중 하나는 함수를 벗어나지 않았기 때문에 두번째 enum에서 s = 'bc'라는 점이다. 바로 전에 letter가 'c' 이기 때문에 두번째 돌때 letter + perm은 cb가 된다. enum(s)의 s가 바뀌었기 때문에... """

 

# a를 제외한 나머지 bc = s[:0] + s[1:]

# b를 제외한 나머지 ac = s[:1] + s[2:]

# c를 제외한 나머지 ab = s[:2] + s[3:]

 

def permute(s):

out = []

#Base Case

if len(s) == 1:

out = [s]

else:

for i, letter in enumerate(s):

for perm in permute(s[:i] + s[i+1:]):

out += [letter + perm]

 

return out

 

o = permute('abc')

print(o)

 

# 결과

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

 

 

 

 

 

# Looping - Fibonnaci

def fib_iter(n):

a, b = 0, 1

for i in range(n):

a, b = b, a + b

return a

 

o = fib_iter(10)

print(o)

 

# 결과

55

 

 

# Fib - not recursion

# Fib - not recursion

fibs = [0, 1]

for i in range(8):

fibs.append(fibs[-2] + fibs[-1])

 

print(fibs)

 

# 결과

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

 

 

# Fib - class 생성

class Fibs:

def __init__(self):

self.x = 0

self.y = 1

 

def __next__(self):

self.x, self.y = self.y, self.x + self.y

return self.x

 

def __iter__(self):

return self

 

fibs = Fibs()

 

for f in fibs:

if f > 10:

print(f)

break

 

# 결과

13

 

# Recursion
# Recursion is the process where a function calls itself
# as a subfunction, with different inputs.
#
# Recursive functions should have:
# - One base case (at least)
# - One recursive case (at least)

def countdown(n):
    if n <= 0: # BASE CASE
        print("Blastoff!")
        return
    else:
        print(n, end=' ')
        countdown(n - 1) # RECURSIVE CASE

countdown(5)

# 결과
5 4 3 2 1 Blastoff!

 

# factorial 예제로 본 iterative, recursive

def factorial_iter(n):
    result = 1
    while n >= 1:
        result = result * n
        n = n - 1
    return result

def factorial_recursive(n):
    if n <= 1:
        return 1
    return factorial_recursive(n - 1) * n

f1 = factorial_iter(5)
f2 = factorial_recursive(5)
print(f1, f2)

# 결과
120 120

 

# Sum a list of numbers both recursion and iteration.
l = [1, 2, 3]

def sum_iter(lst):
    total = 0
    idx = 0
    while idx < len(lst):
        total += lst[idx]
        idx += 1
    return total

def sum_rec(lst, idx):
    if idx >= len(lst):
        return 0
    return lst[idx] + sum_rec(lst, idx + 1)

s1 = sum_iter([1, 2, 3])
s2 = sum_rec([1, 2, 3], 0)

# 결과
6 6