[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / 08q
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes:                    
Labs:          
Wed Apr 27 10:45:45 PDT 2011

CS202 session 08 -- Recursion

Previous -- OO Design

[ 07.html ]

Preparation

Study Chapter 10 and [ Recursive_definition ] on the Wikipedia and do Review Questions from chapter 10.

Enrichment -- Fractals

Enjoy [ Fractals ] (They won't be tested...)

Due in

Hand in one question+answer at the start of class. What ever state your project 1 is in -- hand it in NOW.

Class Work

Introduction -- recursive description of a journey

1. journey::=wriggle straight wriggle.
2. wriggle::= single_step | journey.

Illustration -- Ph D -- Draw a curve on a digital plotter

Given: two functions f and g and a range a..b,

Goal: Display a curve that follows

3. (x,y) = (f(t), g(t)), t : [a..b], with in error ε, using straight line segments.

Binary search

How to find a lion in the bush?

Code: [ binrec.cpp ]

What does the function puzzle do?

[ 08ex.cpp ]

The Fibbonaci numbers done quickly

The book (section 10.6) shows how the defining property of Fibbonaci numbers leads directly to a simple but inefficient program. However Fibbonaci numbers have many other properties, see [ Fibonacci_numbers ] (wikipedia). Here is a faster way to generate fibbonaci numbers: [ fastfibo.cpp ]

. . . . . . . . . ( end of section Class Work) <<Contents | End>>

Classic Example of Recursion -- The towers of Hanoi

[ Towers_of_Hanoi ]

Next -- Algorithms

Bring to class -- a deck of 52 cards! Study [ 09.html ]

Next project due in session 12, bonus session 11. Next quiz in session 12.

Glossary

1. accessor::=`A Function that accesses information in an object with out changing the object in any visible way". In C++ this is called a "const function". In the UML it is called a query.
2. Algorithm::=A precise description of a series of steps to attain a goal, [ Algorithm ] (Wikipedia).
3. class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
4. constructor::="A Function in a class that creates new objects in the class".
5. Data_Structure::=A small data base.
6. destructor::=`A Function that is called when an object is destroyed".
7. Function::programming=A selfcontained and named piece of program that knows how to do something.
8. Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular and free C++ compiler.
9. mutator::="A Function that changes an object".
10. object::="A little bit of knowledge -- some data and some know how". An object is instance of a class.
11. objects::=plural of object.
12. OOP::="Object-Oriented Programming", Current paradigm for programming.
13. Semantics::=Rules determining the meaning of correct statements in a language.
14. SP::="Structured Programming", a previous paradigm for programming.
15. STL::="The standard C++ library of classes and functions" -- also called the "Standard Template Library" because many of the classes and functions will work with any kind of data.
16. Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
17. Q::software="A program I wrote to make software easier to develop",
18. TBA::="To Be Announced", something I should do.
19. TBD::="To Be Done", something you have to do.
20. UML::="Unified Modeling Language".
21. void::C++Keyword="Indicates a function that has no return".