• 들어가기 전에
  : 해당 강좌는 MIT 의 OpenCourseWare 수업을 듣고 내용을 정리한 것이다.
  : 강좌명은 Introduction To Computer Science And Programming In Python, 6.0001 이며 링크는 다음과 같다.
  https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/video_galleries/lecture-videos/

배울 내용

1. Recursion
2. Dictionaries

1. Recursion

What is recursion?

• Algorithmically
  : divide-and-conquer

• Semantically
  : function calls itself

• In programming, goal is to not have infinite recursion
  : must hae 1 ro more base cases
  : must soleve the same problem on some other input with the goal of simplifying the larger problem input

Iteration vs. Recursion

Multiplication

• Iteration

 def mult_iter(a, b) : 
  result = 0
  while b > 0:
    result += a
    b -= 1
  return result

• Recursive solution
  : see a b = a + a (b-1)

 def mult(a,b) : 
  if b == 1:
    return a
  else : 
    return a + mult(a, b-1)

Observation

• Each recursive call to a function creates its own scope
• Flow of control passes back to previous scope once function call returns value

Factorial

• Iteration

def factorial_iter(n) : 
  prod = 1
  for i in range(1, n+1) :
    prod *= i
  return prod

• Recursive

def factorial(n) : 
  if n == 1 : 
    return 1
  else : 
    return n * factorial(n-1)

• Observation
  : Recursion may be simpler, more intuitive, efficient from programmer POV
  : recursion may not be efficient from computer POV

Verify Recursive Code Inductively

• For recursive case, we can assume that code correctly returns an answer for problems of size smaller than b, then by the addition step, it must alswo return a correct answer for problem of size b
  : Thus by induction, code correctly returns answer

Towers of Hanoi

• Recursive 하게 함수를 호출하는 알고리즘의 유명한 예제이다. 자료구조나 알고리즘 공부를 하다보면 초반에 나온다.

Recursion with Multiple Base Cases

• Base cases
  : F(0) = 1
  : F(1) = 1

• Recursive case
  : F(n) = F(n-1) + F(n-2)

  def fib(x) : 
   """
   assumes x an int >= 0
   returns Fibonacci of x
   """
  
   if x == 0 or x == 1 : 
     return 1
   else :
     return fib(x-1) + fib(x-2)

• 자료구조나 알고리즘에서 배우겠지만, 이미 계산했던 base case나 fibonacci value를 다시 계산해야하는 자원 낭비가 일어난다.

2. Dictionaries

What is Dictionary?

• Store paris of data
  : {key, value}
• Looks up the key
• Returns the value associated with the key
• If key isn't found, get an error

my_dict = {} # empty dictionary
grades = {'Ana' : 'B', 'John' : 'A+', 'Denise' : 'A', 'Katy' : 'A'}

print(grades['John']) # A+
# print(grades['Sylvan']) : this code will give error

Dictionary Operations

my_dict = {} # empty dictionary
grades = {'Ana' : 'B', 'John' : 'A+', 'Denise' : 'A', 'Katy' : 'A'}

# add an entry
grades['Sylvan'] = 'A'
print(grades) # {'Ana': 'B', 'John': 'A+', 'Denise': 'A', 'Katy': 'A', 'Sylvan': 'A'}

# test if key is in dictionary
print('John' in grades) # True
print('Daniel' in grades) # False

# delete entry
del(grades['Ana'])
print(grades) # {'John': 'A+', 'Denise': 'A', 'Katy': 'A', 'Sylvan': 'A'}

# get all keys
print(grades.keys()) # dict_keys(['John', 'Denise', 'Katy', 'Sylvan'])
# no guaranteed order
print(type(grades.keys())) # <class 'dict_keys'>

# get all values
print(grades.values()) # dict_values(['A+', 'A', 'A', 'A'])
# no guaranteed order
print(type(grades.values())) # <class 'dict_values'>

Dictionary Keys and Values

• Values
  : any type (immutable and mutable) (even other dictionaries)
  : can be duplicates
• Keys
  : must be unique
  : immutable type

List vs. Dictionary

• List
  : ordered sequence
  : look up elements by an integer index
  : indices have an order
  : index is an integer
• Dict
  : matches keys to values
  : look up one item by another item
  : no order is guaranteed
  : key can be any immutable type