Tue Nov 26

Aside ...the perils of object oriented coding

• The faster you unlearn OOP the better | HackerNews discussion

in class

I've attached the programs we did in class, length.py and max.py. I also showed a towers of hanoi program.

recursion

Definition: recursion.
See "recursion".

Discussion topics :

• the basic idea : a function that calls itself, along with a stopping condition
• great for self-similar data structures : lists, graphs, ...
• recursive algorithms :
  • linear search ... look at each element in turn
  • binary search (if ordered) ... explicit loop vs recursive implementation
• time (i.e. number of steps) efficiency : log base 2 vs linear vs exponential
• wikipedia

Code examples :

• textbook binary search code
• my recursion examples

Just for fun :

• http://www.contextfreeart.org/
  • spiral
  • fern
  • arboreal tree
  • foggy tree
  • fractal flower
  • ancient script
• Documentation :
  • shape adjustments
  • path declarations
• Summary :
  • cheatsheet

Recursion Class Exercise :

Write a recursive function that finds the maximum value of a list.
The idea is to think of a list recursively as 
  (list) = (first_element, list)
and so max(list) = max( first_element, max(list) )
What is the stopping condition ?

attachments

		last modified	size
	length.py	Thu Apr 25 2024 12:55 pm	493B
	max.py	Thu Apr 25 2024 12:55 pm	470B