CS计算机代考程序代写 ant data structure CS 345
CS 345
CS 345
Lecture 4
Lab #1
Lab #1
Circle will be called ONCE.
Lab #1
Last time: conditional branching
class WhileIfDemo {
public static void main(String[] args){
int count = 1;
while (count < 11) {
System.out.print("Count: " + count);
if (count % 2 == 0) {
System.out.println(“ is even.”);
} else {
System.out.println(“ is odd.”);
}
count++; }
}
}
Conditional branching makes sense in functional programming, but iterative control flow structures (for and while loops) do not, because they mutate state. Repetitive evaluation in functional programming requires recursion.
Today’s Topics
Functional programming in Racket, cont’d with…
Lists as recursive data structures
Recursion
Participation Quiz
Lists in Racket
You can declare a list in two ways:
‘(1 2 3 4)
(list 1 2 3 4)
Both of these are “syntactic sugar” for:
(cons 1 (cons 2 (cons 3 (cons 4 ‘() ))))
At the base of all lists is the empty list, and items are “consed” onto
the empty list. Cons stands for “construction”.
Lists are “recursive data structures”
You can always speak of the “head of the list” and the “rest of the list.”
Head: 1
Rest of the list: ‘(2 3 4)
Looking at the “rest of the list,” you can again speak of the “head of the list” – 2 – and the “rest of the list” (3 4)
This nested structure is what is meant by “recursive data structure”
Lists
cons = construction of a list
car = first item in the list
cdr = the rest of the list
‘() = empty list, the base of all lists
Lists
(define my-list (list 1 2 3 4 5 6))
Given this list, what gets returned?
> (car my-list)
1
> (cdr my-list)
‘(2 3 4 5 6)
> (car (cdr (cdr my-list)))
3
> (cons 1 my-list)
‘(1 1 2 3 4 5 6)
> (cons 0 (cons 1 my-list))
‘(0 1 1 2 3 4 5 6)
How do you move through lists?
Whereas imperative languages can mutate an index in a for-loop, functional languages can’t mutate state and instead accomplish repetition solely through recursion.
Recursion on lists: Evaluate the car of the list and call the function again on the cdr of the list. Handle your base base.
(define (length ls)
(if (empty? ls)
0
(+ 1 (length (cdr ls)))))
> (length (list 1 2 3 4 5 6))
> 6
Tracing Recursion in Racket
Let’s trace the evaluation steps for:
(length (list 1 2 3))
(+ 1 (length (list 2 3)))
(+ 1 (+ 1 (length (list 3))))
(+ 1 (+ 1 (+ 1 (length ‘()))))
(+ 1 (+ 1 ( + 1 0)))
(+ 1 (+ 1 1))
(+ 1 2)
3
Learning how to trace your code like
this is a good idea. This is how you
can get yourself “unstuck” when
faced with a difficult recursion problem.
The recursive thought process:
“Return the sum of the items of a list”
(list 1 2 3) 6
(1 (2 (3 empty)))
(+ 1 (+ 2 (+ 3 0)))
(define (sum ls)
(if (empty? ls)
0
(+ (car ls) (sum (cdr ls)))))
Think of the list as a recursive data structure
Your answer, as an expression
Base case
Recursive case
Example #1: Factorial
5!
5 * 4 * 3 * 2 * 1 = 120
(* 5 (* 4 (* 3 (* 2 1))))
(define (factorial x)
(if (= x 1)
1
(* x (factorial (- x 1)))))
Example #2: Ant population
Imagine an ant population that grows by 15% every day, starting at 80 ants. How many days will it take to grow to 990 ants?
Day 0 Day 1 Day 2 Day 3 etc…
80 92 105.8 121.67
This is a classically “recursive sequence,” in the mathematical sense: the next value is defined by the value before it.
next = previous * 1.15
Example #2: Ant population
Returning a new list
Previous examples returned one value.
How do we return a new list, where each item in the new list is some evaluation of the items in the input list?
Use cons in the recursive case, and return an empty list in the base case.
Example #1: Given 3, return (list 3 2 1)
3 (list 3 2 1)
3 (cons 3 (cons 2 (cons 1 ‘())))
(define (get-list x)
(if (= x 0)
‘()
(cons x (get-list (- x 1)))))
Participation Quiz: negate-all
As in:
> (negate-all (list 1 2 3 4))
> ‘(-1 -2 -3 -4)
Functional “negate-all”
(define (negate-all ls)
(if (empty? ls)
‘()
(cons (- (car ls)) (negate-all (cdr ls)))))
> (negate-all (list 1 2 3 4))
> ‘(-1 -2 -3 -4)
Work on first two problems of Lab 2
(Asynchronous)
/docProps/thumbnail.jpeg
