CSC148H1 Lecture Notes - Lecture 26: Memoization, Binary Tree
CSC148: Lecture 25: Redundancy and Efficiency
References: Code seen in the pictures can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter
Redundancy
- Some recursive functions “write themselves”
o You have to write base case and general case from a definition
- Fibonacci numbers:
o The first 2 numbers in Fibonacci sequence are either 1 and 1, or 0 and 1,
depending on the chosen starting point of the sequence and each subsequent
number is the sum of the previous two
o Sequence of Fn of Fibonacci numbers defined as:
▪ If n < 2: Fn = 1
▪ Else: Fn = Fn-1 + Fn-2
- Easy to implement this using recursion but it is not efficient
o Uses repeated calculations:
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
References: code seen in the pictures can be found on the csc148 website: http://www. teach. cs. toronto. edu/~csc148h/winter. Some recursive functions write themselves : you have to write base case and general case from a definition. If n < 2: fn = 1: else: fn = fn-1 + fn-2. Easy to implement this using recursion but it is not efficient: uses repeated calculations: Used primarily to speed up computer programs by storing results of expensive function calls and returning cached result when the same inputs occur again. Considerations: how you implement matters, can code fast, inefficient code, key is to identify which parts are inefficient, how time grows with input. Any recursive function can be written iteratively. Recursive functions are not more efficient than iterative equivalent. If nature of the problem is recursive, writing it iteratively can be: more time consuming. In the following: list, tree, binary tree, bst.
