09/21/05 Lecture Notes for CISC181

P. Conrad Fall 2005

(0) ACM meeting

7:30 Gore 104

Excerpt from video about Gaming industry
(maybe.. at least I think that's what they
have planned...)

Website:  http://www.ecl.udel.edu/~acm

Email: acm@ecl.udel.edu




(1) Online versions of textbooks

Savitch:  ($24)

http://www.aw-bc.com/codemate/

Andersen:  ($around 35 or 36?)

http://ebooks.primisonline.com

(2) Recursion

Why: because it works well on trees.

factorial

fibonacci

reversing a string

What you need to know about recursion.

A function is recursive if there is
a call to the function itself inside
the definition of the function:

int factorial(int x); // function prototype

int factorial(int x)
{
  if (x == 0)
    return 1;
  else
    return x * factorial(x-1);
}

This function is recursive because there
is a function call to factorial INSIDE
the definition of factorial:

factorial(x-1); is a call to factorial

the whole thing above is the function definition.


Factorial of x

typically written x!

[At this point in the lecture, something mysterious happened, and
Prof. Conrad was kicked off the internet.  Perhaps someone in Redmond
Washingon heard him say something they dididn't like.  Just kidding!!!
I LOVE MICROSOFT.  Kiss kiss, hug hug.]

So, he used the auto-save feature of Emacs, thus, to get back what he had typed:

#09.21.txt#  09.21.txt    09.21.txt~
> mv #09.21.txt# 09.21.txt
mv: overwrite 09.21.txt (yes/no)? yes
> 

So.. 

[A tip in response to a student question: to wrap a 
paragraph in emacs, when you are are in text mode,
use "M-q" meta-q, escape-q.  You can also use the
same key in C++ mode to fix up comments... ]

5! = 5 *(4 * 3 * 2 * 1)

4! =    (4 * 3 * 2 * 1)

5! = 5 * 4!

237! = 237 * 236!

1! = 1 * 0!

0! is defined as one.

BUT...

is it true that

0!= 0 * (-1)!   NOT TRUE

So, we treat 0 as a special case.

In fact, we treat 0 as a BASE CASE.

The way recursion works is that
you need two parts:

(1) Base case

(2) Recursive call that moves you
    in the direction of the base case.

Look at factorial.cc