minte9
LearnRemember / ALGORITHMS



Stack 

 
""" A stack stores multiple values like a list. 
Stacks are LIFO data structure (last in, first out)
"""

cards = []

# Append cards at the end
cards.append('5'); print(' '.join(cards))
cards.append('3'); print(' '.join(cards))
cards.append('7'); print(' '.join(cards))

# Remove last
cards.pop(); 

# Output the remaining list
print(' '.join(cards)) 

"""
    5
    5 3
    5 3 7
    5 3
"""

Line Remembering 

 
""" Programming languages remember the line of code that called a function. 
It returns to that line when the function finishes its execution.
"""

def A():
    print('A -> Line 01')

    
    print('A -> Goto B and remember the line in A')
    B()

    print('A -> Line 02');

def B():
    print('B -> Line 01')

A()

"""
    A -> Line 01
    A -> Goto B and remember the line in A
    B -> Line 01
    A -> Line 02
"""

Frame Objects 

 
""" A Frame contain information about a single function call.
Frames are created and pushed onto the stack when function is called.
When the function returns, that frame is popped off the stack.
"""

# Frame's number
no = 0

def A():
   global no
   no += 1

   i = no
   print(f"Function A / Frame {i}")

   # Push anew frame onto the stack
   B()

   print(f"Function A / Frame {i}")
   return

def B():
   global no
   no += 1

   print(f"Function B / Frame {no}")
   return


# Push first frame onto the stack (function call)
A()

# Push new frame onto the stack
B()

"""
   Function A / Frame 1
   Function B / Frame 2
   Function A / Frame 1
   Function B / Frame 3
"""

Base Case 

 
""" When using recursion, to avoid a crash, there always must be a base case. 
The function stop calling itself and just returns.

The code in a recursive call can be split in two parts, 
before the recursive call and after recursive call.
"""

def show_frame(i=0):
  sep = i * " "

  if i == 3:
    print(f"{sep}-- Base case --")
    return

  print(f"{sep}Frame {i} / Recursion {i}")

  # Recursion
  show_frame(i+1)

  print(f"{sep}Frame {i} / Return")
  return

show_frame()

"""
  Frame 0 / Recursion 0
    Frame 1 / Recursion 1
      Frame 2 / Recursion 2
      -- Base case --
      Frame 2 / Return
    Frame 1 / Return
  Frame 0 / Return
"""

Stack Overflow 

 
""" The limit of calls is called maximum recursion depth.
Stack overflows don't damage the computer, it just terminate the program.
For Python, this size is set to 1000.
"""

def repeat():
    repeat()

repeat() # RecursionError: maximum recursion depth exceeded






Questions and answers




What LIFO means?

  • a) Data list where last in, first out
  • b) List of functions

Which one represents the state of function call?

  • a) frame object
  • b) call stack

Frames are created and pushed onto the stack:

  • a) when function is called
  • b) when the function returns

What is the stack overflow limit in Python?

  • a) 3000
  • b) 1000

How do you avoid a crash when using recursion?

  • a) There must be a base case
  • b) There must be stack limit


References