- ALGORITHMS //
- RECURSION //
-
Call Stack
- Iterative Approach
- Memoization
- Head Tail
Click to Flip Card
Call Stack
What is the call stack? What does frame object represent? What is the stack overflow limit in Python? How do we avoid a crash when using recursion?
Line Remembering
Programming languages remember the line that called the function.
""" Programming languages remembers the line of code that called
a function. It returns to that line when the function
finishes its execution.
"""
def line_remembering_function():
print('Line 08')
goto()
print('Line 10')
return
def goto():
print('Line 14 - return to first function')
return
line_remembering_function()
"""
Line 08
Line 14 - return to first function
Line 10
"""
Call Stack
The call stack is used to manage the order of function calls.
""" Stacks
A stack stores multiple values like a list.
Stacks are LIFO data structure (last in, first out)
"""
cards = []
cards.append('5'); print(' '.join(cards))
cards.append('3'); print(' '.join(cards))
cards.append('7'); print(' '.join(cards))
cards.pop(); print(' '.join(cards)) # Last in, First out
"""
5
5 3
5 3 7
5 3
"""
Frame Objects
A frame object is a data structure that represents the state of a function call.
""" 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,
and the previous frame object becomes the current one,
resuming the execution of the calling function from where it left off.
"""
def frame_objects(i=1):
print('A Frame', 'No.', i)
second_func(i+1)
print('A Frame', 'No.', i)
return
def second_func(i):
print('B Frame', 'No.', i)
third_func(i+1)
print('B Frame', 'No.', i)
return
def third_func(i):
print('C Frame', 'No.', i)
return
frame_objects()
"""
A Frame No. 1
B Frame No. 2
C Frame No. 3
B Frame No. 2
A Frame No. 1
"""
Stack Overflow
The limit of stack size is 1000 function calls in Python.
""" 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
Base Case
To avoid a crash there must be a base case.
""" Base case
To avoid a crash, there must be a base case,
where 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=1):
print('Frame', i)
if i == 3:
print(i * " ", 'Base case')
return
print(i * " ",'Recursive case', i)
show_frame(i+1)
print(i * " ",'Recursive return', i)
return
show_frame()
"""
Frame 1
Recursive case 1
Frame 2
Recursive case 2
Frame 3
Base case
Recursive return 2
Recursive return 1
"""
Last update: 129 days ago
