[SOLVED] 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.Todays TopicsFunctional programming in Racket, contd withLists as recursive data structuresRecursion Participation QuizLists in RacketYou 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 structuresYou can always speak of the head of the list and the rest of the list.Head: 1Rest 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 structureListscons = construction of a listcar = first item in the listcdr = the rest of the list() = empty list, the base of all listsLists(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 cant 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
Lets 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(3empty)))

(+ 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 0Day 1Day 2Day 3etc
8092105.8121.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