Many containers are implemented using an array. You have the dictionary object, and the backing store, which is the array. In our dictionary class, we use our custom Array class as the backing store.

Continue reading →

As per our definition of recursion from a previous lecture, an array is defined as an element followed by an array. In some languages, once you declare a variable as an array a of size 10, you can’t redeclare a[1] as an array of 9 elements. However, C++ lets the programmer manipulate pointers in this way.

Let’s write a contains function using the recursive definition that searches for some value. We may find the value as the first element of the array, in which case we return true since the value is found, or the array may be of size zero, in which case the value is not in the array and we return false. If neither are true, we call the contains function again on the same array but started at the next element and on the array size decreased by one. The value parameter remains the same since the value being searched for does not change.

bool contains(int arr[], int n, int val){

  if(n == 0) return false;        // Escape clause

  if(arr[0] == val) return true;  // Second escape clause

  return contains(a+1, n-1, val);

}

The line if(n == 0) return false; is called our our escape clause. If the size of the array is 0, it’s empty, and it obviously doesn’t contain the value we’re looking for. Therefore, we escape the function and do not call contains recursively, even though the value is not found. Technically, the second line, if(arr[0] == val) return true; is also an escape clause since it causes us to escape the function. If we find the element, we return true.

Another way of writing this function is to check for the last element first and working your way towards the beginning of the array with each successive recursive call.

bool contains(int arr[], int n, int val){

  if(n == 0) return false;          // Escape clause

  if(arr[n-1] == val) return true;  // Second escape clause

  return contains(a, n-1, val);

}

The only difference here is that in the recursive call we’re starting with the last element of the array instead of the first element. The size is still decreased by one and the value still remains the same.

Can other languages allow you to manipulate pointers like this? Most languages offer “real” array classes and so they usually don’t.

Here’s how you print out an array recursively:

void print(int a[], int n){

 if (n == 0) return;

 cout << a[0] << " ";

 print (a+1, n-1);

}

Notice the magic of local variables. In the second function call, a+1 becomes a. It’s really iteration.

Tail recursion is a function where the only recursion happens at the end of the function. Consider this:

void print(int a[], int n){

 if (n == 0) return;

 print (a+1, n-1);

 cout << a[0] << " ";

}

This function works in the reverse of the previous print function. First we make the recursive call. Then we start printing. This prints the array in reverse. The magic happens in the local variables.

Remember our code from Lecture 5 to read a file in and print it out? We’re writing that recursively. Note that an istream is a “supertype” of ifstream and cin. Also, files are streams, just like cin. (More on that in CISC 3130.)

//Read a file or input stream and print.

void print(istream &is){

  int num;

  if(!is) return;

  cout << num;

  print(is);

}

Streams are recursive structures, just like arrays.

Every time you call a function recursively, you take some room on the stack. This is like death by a thousand paper cuts. Tail recursion is more efficient than head recursion. However, most compilers optimize head recursion into a loop.

Now we’re writing a find function.

int find(int arr[], int n){

 if(n == 0) return n -1;

  if(arr[0] == val) return 0;

  int resut = contains(a+1), n-1, val);

  if(result == -1) return -1;

  return result + 1;

}

Here’s how to find if a character is contained in a string, recursively:

bool contains(string s, char s){

  if(s.length() == 0) return false;

  if(c == s[0]) return true;

  return contains(s.substr(1),c);

}

The strings madam and racecar are palindromes (Here’s a (link) to a bunch of palindromes.) In genetics and biology, searching for palindromes seems to be of interest.

Towers of Hanoi

The Towers of Hanoi is game or puzzle and presents a great recursion problem. The goal of the Towers of Hanoi is to move all of the discs from the first tower to the third tower using an intermediary tower. However, the catch is that a larger disk can never be on top of a smaller disk and that more than one disk at a time cannot be moved. There is a legend that says that priests in a Hindu temple have three towers and 64 discs. They move the discs religiously according to the above rules until they solve the Towers of Hanoi, at which point the world will end. The legend seems quite ominous until one calculates how many turns it would actually take the priests to solve the puzzle, assuming the legend is true. The following is a visual simulation of the Towers of Hanoi:

      |         |         |

   1 _|_        |         |

  2 __|__       |         |

 3 ___|___      |         |

4 ____|____     |         |

Let’s name the above three towers left middle, and right, respectively. It is important to note that if we solve Towers of Hanoi from left to right using the middle as a holding tower, we can also solve it from left to middle using the right as a holding tower.

Here’s our function to solve the Towers of Hanoi:

void solveTowers(int n, string sourceTower, string destTower,
string holdingTower) {

        if (n == 1)

               cout << "Move disc 1 from " << sourceTower << " to "
                    << destTower << endl;

        else {

               solveTowers(n-1, sourceTower, holdingTower, destTower);

               cout << "Move disc " << n << " from " << sourceTower
                    << " to " << destTower << endl;

               solveTowers(n-1, holdingTower, destTower, sourceTower);

        }

}

It would take the priests at least (2^64)-1 turns to solve the puzzle, which calculates to be 18, 446, 744, 073, 709, 551, 615. It’s clear why Towers of Hanoi isn’t the inconvenient truth. Until a better solution to the game comes out, Al Gore can rest peacefully.

As a challenge, print the above function recursively with braces. Make sure to test your code because if you write your code and you think you wrote it correctly, you probably didn’t.

To the pythagoreans, the square root of 2 was unfathomable. They took the Pythagorean Theorem seriously enough that when one of their members leaked it, they tried to kill him.

Learn to speak boolean. Instead of writing this code:

bool b;

if(b==true) /* ... */

Write this:

if(b)

That’s “talking the language of boolean”. Another example of this:

return x < y; //returns true if x<y and false otherwise

You’re about to learn another language: Recursion.

As it turns out, one of the favorite things that faculty members in general like to do is do traces. Write a program called f that two compares two parameters. They’ll have:

int f(int x, int y){

  if(x < y) return...

}

In 1110, we made boxes. When dealing with recursion, you can’t simply use a single box. You need columns.

x | y | return value

--------------------

5 | 6 | f

7 | 4 | f

6 | 6 | f

The secret to learning programming is not compiling. It’s the problem solving and the creation of an algorithm. It’s an exercise – in logic.

Traces work because you work through your algorithm and you figure it out itself. Debugging usually isn’t tracing. You might add print statement to see what some of your values are, but you’re not printing all 30 values in your programs.

You don’t look at recursion by doing traces. Let’s take another look at Monday’s factorial problem.

What happens if we have a negative number in recursion? It will blow up on you. For the most part, we’re working with positive numbers.

 n! = {n*(n-1), n≠0}

Here’s the first 6 factorials:

1,  1,  6,  24, 120, 720

0!, 2!, 3!, 4!, 5!, 6!

Let’s see the code for factorial. The code for factorial is amazingly like our definition of recursion above:

long fact(int n){

  if(n == 0 || n == 1) return 1;

  return n * fact(n-1);

}

On Monday we used the iterative solution. (To iterate is to loop.) For every iterative solution to a problem, there’s a recursive solution.

You can’t create your own postfix operator. You can use what the language gives you. So we can’t make a ! operator.

Occum was a philosopher in the 11th century. Occum’s razor states that the solution to a problem is often the simplest explanation. Professor Weiss has two favorite Sesame Street episodes:

Here’s the first one: There’s a bunch of kids standing in the yard. There’s a lawn mower in the gutter. There’s whipped cream in the windows. The mother comes out and asks the kids what happened. They said that there’s an alien in a spaceship that came down and made the mess. The mother applies Occum’s razor and takes the kids inside and spanks them, since it’s the simplest things to do. As the camera pulls back, sure enough, there’s a spaceship behind the house.

Second story from Sesame Street: There’s a wall in a kingdom. someone is standing there and wants to get over the wall. There’s a bunch of blocks lying around. He takes a block an puts it next the wall and climbs on tip and still can’t reach top. So he takes another block and stacks it on the first one.

Take it one step at a time.
- Satan

Recursive definition of stairs: A flight of steps is either no steps at all, or a single step followed by a flight of steps. A sink full of dishes: Either don’t do anything, or do one and pass off the job and have the next guy do it. The next does the same. Famous statement from the 70′s: “Today is the first day of the rest of your life.” All it is is a statement of recursion. Professor Weiss doesn’t understand why it’s inspirational.

Recursion is all about “taking it one day at a time.”

Hell is a flight of steps. Satan says “take it one step at a time”. The problem is that those stairs have no end. Hell’s kitchen is a sink full of dishes.

Recursive code needs the “escape clause” or the “base case”. If not, you’ll never break out of your recursion. Once we hit the escape clause, you’ll start returning. (This is like a pearl diver, who goes down a little at a time, then goes up a bit, then goes back down.)

Let’s trace the fact() function:

int main(){

  long l = fact(3);

  cout << l << endl;

  return 0;

}

Here’s the trace:

main      |      fact

------------------------

l         | n    retval

-         | --   ------

          | 3           fact(3)

          | 2           fact(2)

Local variables get created upon entry to a function. We have two local n variables on the stack. If there’s one trace to keep in your head, keep the “stack trace” in your head.

main      |      fact

------------------------

l         | n    retval

-         | --   ------

          | 3           fact(3)

          | 2           fact(2)

          | 1           fact(1)

(The instruction counter is a local variable of sorts too.)

When we hit fact(0) we return 1:

main      |      fact

------------------------

l         | n    retval

-         | --   ------

          | 3           fact(3)

          | 2           fact(2)

          | 1      1    fact(1)

          | 0      1    fact(0)

Now we return to the next fact() call.

main      |      fact

------------------------

l         | n    retval

-         | --   ------

          | 3      6    fact(3)

          | 2      2    fact(2)

          | 1      1    fact(1)

          | 1      1    fact(0)

Read the retval column from bottom to top to see how you’re climbing the call chain.

Solving recursive problem is about solving problems by redefining a problem as a simpler version of itself.

The exam is a week from Monday. Here’s some recursion problems:

A sink full of dishes is recursive. It’s defined as a dish followed by a sink full of dishes.
The Fibonacci sequence can be calculated recursively.

If you are going to write an iterative version or a recursive version, Professor Weiss says that the recursive version wins any day.

Here’s the definition of the Fibonacci sequence:

fib(n)={fib(n-1)+fib(n-2), n if n≤1}

As code:

int (int n){

  if(n <=1) return n;

  return fib(n-1)+fib(n-2);

}

Challenge: Do this iteratively.

Sulu is the helmsman in Star Trek. Every so often, they’d go into a black hole and he has 45 seconds to program the ship away from the black hole. Recursion is much faster, and much easier to get right.

Before recursion worked, you had to save memory addresses before going deeper into the call stack.

The actual code for fact():

return n == 0 ? 1 : n * fact(n-1);

The code for Fibonacci:

return n <= 1 ? n : fib(n-1) + fib(n-2);

Trust the dark side. Use recursion.

- Prof. Weiss

What about getting an odd number?

bool isOdd(int n){

  if(n == 0) return false;

  if(n == 1) return true;

  return isOdd(n-2);

}

Here’s the same thing as a “work of art”:

return n == 0 ? false : n == 1 ? true : isOdd(n-2);

Here’s another way to write isOdd():

bool isEven(int n){

  if(n == 0) return true;

  return isOdd(n-1);

}

bool isOdd(int n){

  if(n==0) return false;

  return isEven(n-1);

}

These functions are called mutually recursive functions. This not thinking in recursion, it’s thinking fluently in recursion.

Next up, exponents:

long toThePowerOf(int x, int y){

  if (y == 0) return 1;

  return x * toThePowerOf(x, y-1);

}

What does it mean for x to be greater than y?

Think about two piles of boxes. If you knock out the bottom box with a baseball bat, and one pile disappears and one does not. For a recursive solution, go through each number and subtract one. See which one hits zero first.

Suppose I want to find a name in a phonebook. (Why a binary search?) In a binary search, you compare the name and keep cutting distance between the start and end in half. You only have to look at what’s left. A recursive binary search, psuedocode:

bool binSearch(int val, int arr[]){

  //if arr is empty return false.

  //if(val equals middleElement) return true

  //if val is less than middle element, return binSearch(val, arr[:middleElement-1])

  //else, binSearch(val, arr[middleElement+1:];

}

That, ladies and gents, is recursion.

This is the overloaded insertion operator of the insertion class:

friend std::stream &operator <<(std::ostream &os, const Array &array);

It is declared as a friend because a friend  function is one that is not part of the class, but has access to the class’s private data members.

Assignment is when you have an existing object and you’re assigning a new value to it. Hence, there’s no such thing as “assignment” in a constructor. That’s called “initialization”.

The default value for copying an object is a simple copy of the values.

“Aliasing” is when two pointers point to the same object. The problem with this is if you have an array as a member variable. Changes to one alias affect the other. We need what is called a “deep copy” of our member variable.

Why do we write custom constructors to copy pointers?
A: To perform a deep copy.

When you make a copy constructor to deep copy, you need to have a corresponding destructor to clean up the “deeply copied” memory. If you don’t create that, you lose the memory.

Assignment says “take the value on the right hand side and store it in the location on the left side.

Consider:

a1[12]++

In this case, a1[12] is both the lval and the rval.

Consider:

Array a1;

Array arr = a1 + 4;

In the second line above, the + operator is invoked. Then, the copy constructor is invoked. We end up with two copies.

When temporary objects go out of scope, their destructor gets called.

If I have three books, War & Peace, Hunger Games, and Yellow Pages, there are 6 ways to arrange them on the shelf.

Recursion

In general, n * (n-1) * (n-2) … 1 is called n factorial. We write factorials as n!.

Let’s create a function to calculate factorials:

long fact(int n){

for(int i  = 0; i

We can’t initialize i to zero, because multiplying by it will be a problem. Also, we need a temporary variable to hold the result. Let’s try again:

long fact(int n){

long result = 0;

for(int i  = 0; i

Again, result is zero, so multiplying by it will always return zero. If we change the result to 1, it works.

long fact(int n){

long result = 1;

for(int i  = 0; i

What is the value of (n-1)! ?

n!/n = (n-1)!

Here’s an alternate way:

long fact(int n){

if(n == 0 || n == 1) return 1;

return n * fact(n-1);

}

This works because of recursion. The secret sauce here is local variables. Recursion and local variables.

Let’s continue working on the Array class with some overloaded operators.

If the only thing a class member function does is return a data member without changing anything in the class, the function is said to be immutable. If a class member function changes or mutates members in the class, the function is said to be a mutator function.

One of the times a copy constructors is called is when you’re creating an object from another object of the same class. For example:
Array b = a;

We write our own copy constructor if a data member is a pointer. Otherwise, the pointer in the new object will be pointing to the same memory as the old pointer. We create what is called a “deep copy” of the object. A copy that is made without a copy constructor is called a “shallow copy.”

When writing destructors, make sure to remember to delete “native” arrays (and all objects which you’ve allocated) using the “delete” keyword. When deleting arrays, don’t forget thy square braces, lest the compiler burn you later on.

To delete array a, your destructor would look like this:

delete[] a;

When you say

b=a;

You’re actually saying this:
b.operator=(a);

In C++, the this keyword refers to the pointer to the object which is being operated on. We don’t want to return the pointer, though. We want to return a reference. So we return *this.

In Java you don’t have to worry about memory management. It’s handled by something called garbage collection. The garbage collector is the part of Java that handles this.

What happens here in the following code?
a=a;

All kinds of things, from broken member arrays caused by improper copying, to memory leaks. Unless we handle this correctly in our copy constructor. A memory leak is when you allocate memory, for example with “new”, and then remove the pointer to that memory without cleaning it up. You can’t access it anymore but neither can any other program. If this builds up, your machine can run out of memory can crash.