In this lab we will dive into functional programming and recursion.
In short, recursion is idea of having a procedure solve some big problem by
making it a little bit smaller somehow and then calling itself.
When it calls itself, it makes the problem smaller yet again. This
continues until the problem is small enough to be trivially solved.
Recursion can be hard to get used to if you have never used it before.
Some things to remember when programming recursively are:
Remember to have a base case. Your recursion should reach a point where it
no longer needs to call itself to get an answer. At some point the problem
should be trivial enough to just output an answer.
Always make your problem smaller. Whenever you make a recursive call make
sure your arguments are smaller than what they were to begin with. If they
aren't then you can get yourself into some nasty infinite loops.
Lastly trust the recursion! Don't overthink the problem. If your recursion
makes sense and you've followed hints 1 and 2 you probably have working code.
You don't always need to trace through the recursion to make sure your procedure
works as you expect it to.
do this in section if possible; finish the rest at home
People who know Scheme: Don't use the CS 3 higher-order procedures such as
every in these problems; use recursion.
The Return of new-if
Most versions of Lisp provide and and or
procedures like the ones we've seen.In principle there is no reason why these
can't be ordinary procedures, but some versions of Lisp make them special forms.
Suppose, for example, we evaluate (or (= x 0) (= y 0) (= z 0))
If or is an ordinary procedure, all three argument expressions will
be evaluated before or is invoked. But if the variable x
has the value 0, we know that the entire expression has to be true regardless of
the values of y and z. A Lisp interpreter in which
or is a special form can evaluate the arguments one by one until
either a true one is found or it runs out of arguments.