-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1.2-presentation.rkt
153 lines (105 loc) · 4.35 KB
/
1.2-presentation.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
;; This section is about consequences
;; Linear Recursion and Iteration
;; Linear Recursive PROCESS
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
(factorial 6) ------------------------.
(* 6 (factorial 5)) |
(* 6 (* 5 (factorial 4))) |
(* 6 (* 5 (* 4 (factorial 3)))) |
(* 6 (* 5 (* 4 (* 3 (factorial 2))))) |
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1)))))) |
(* 6 (* 5 (* 4 (* 3 (* 2 1))))) |
(* 6 (* 5 (* 4 (* 3 2)))) |
(* 6 (* 5 (* 4 6))) |
(* 6 (* 5 24)) |
(* 6 120) |
720 <-------------------------------'
;; Linear Iterative PROCESS
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
(factorial 6) -----.
(fact-iter 1 1 6) |
(fact-iter 1 2 6) |
(fact-iter 2 3 6) |
(fact-iter 6 4 6) |
(fact-iter 24 5 6) |
(fact-iter 120 6 6) |
(fact-iter 720 7 6) V
720
;; They both are recursive PROCEDURES
;; The second is iterative because its state
;; is entirely captured by: product counter max-count
;; In C, this would consume a lot more memory, it is not tail-recursive.
;; Tail-recursive means you can define an iterative process using
;; a recursive procedure, and have it not consume more than one iteration
;; of memory.
;; Tree Recursion
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
..<............ fib5 <..........
... ___________/ \___________ .
... / . ..... \ .
.. fib4 . . . . . fib3 .
.. ____/. \____ .. . __/ \__ .
.. / . . .. \ . .. / . . \ .
.. fib3 . . fib2 . . fib2 . . fib1 .
.. / . \ . . / \ . . / \ ... . | .
.. / . . \ . . / . \ . . / . \ . . 1 .
. fib2 . . fib1. .fib1 . fib0 . .fib1. . fib0 . . .
. / \ . . | . . | . . | . . | . . | . ..
. / . \ . 1 . . 1 . . 0 . . 1 . . 0 ..
. fib1 .. fib0.. . . . . . . . .. .
. | . . | . .. ... . . .... ..
. 1 . . 0 .
. . . .
... ..
;; Steps grows exponentially from the input
;; Space grows linearly
;; Redefine it to use an iterative process over recursive
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
;; Tree-recursion is useful in other domains.
;; Notice how we can improve our algorithms once we
;; know where they fall short. E.G. Once we knew how many
;; steps our tree recursive fib was going to take, we could
;; redesign it to use iteration.
;; Example: Counting change
;; Orders of Growth
;; Theta is the "middle" bound of growth, both for space and steps
;; Big-O (omicron) - Upper bound
;; Big-Θ (theta) - "Between" bound
;; Big-Ω (omega) - Lower bound
;; Big-O is often used in CS as a "proxy" for Big-Theta
;; The linearly recursive factorial is:
;; Θ(n) - steps
;; Θ(n) - space
;; Linearly iterative factorial is:
;; Θ(n) - steps
;; Θ(1) - space
;; Tree-recursive Fibonacci is:
;; Θ(golden-ratio ^ n) - steps
;; Θ(n) - space
;; Why do they start you on orders of growth as the second thing
;; right after syntax?
;; Examples: Exponentiation, GCD, Primality,
;; Favorite Part of the minor section?
;; Any "ah ha!" moments?
;; Worst part?
;; Hardest?
;; Is studying orders of growth valuable still today?