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