Recursion Examples

So, allow me to ramble on in an unstructured form with the idea of capturing the different types of cannonical recursion examples.  When you hear beknighted C++ developers talk, much is made of multiple inheiritance or recursion.  Yet, on a daily basis neither really comes up too frequently.  The latter, however, when it does appear, usually is the ONLY way to solve some problem.  Before I attmpt to topologically capture which recursion problems can be solved with which idioms, I want to consider the mathematical foundations behind a recursion.  How many people have an intuitive notion for the running time of Insertion sort without having to the formal inductive proof?  Who wants to continue this expansion?

Chad Salinas Recursion for Insertion Sort Example

Need idiomatic recursion examples for:

• Exhaustive Permutation
• Exhaustive Subset
• Recursive Backtracking
• Others???

I have only Julie Zelenski at Stanford to thank for any of the following 2 C++ code examples:

1.  Exhaustive Permutation example

void RecPermute(string soFar, string rest)
{
if (rest.empty()) {
cout << soFar << endl;
} else {
for (int i = 0; i < rest.length(); i++) {
string remaining = rest.substr(0, i)
+ rest.substr(i+1);

RecPermute(soFar + rest[i], remaining);
}
}
}

2.  Exhaustive Subset example

void RecSubsets(string soFar, string rest)
{
if (rest.empty())
cout << soFar << endl;
else {
RecSubsets(soFar + rest[0], rest.substr(1)); // include first char
RecSubsets(soFar, rest.substr(1)); // exclude first char
}
}

Chad Salinas

Let’s Create a Memory Leak

Doing due diligence of VC-baked software startups, I get to see a lot of code like this:

SalesOrder * Order = new[100]; …

delete Order;

The developer has just created a memory leak.  The destructor ~SalesOrder() will only delete the first order, orphaning the remaining 99 on the heap.  The correct call to release all the memory of the 100 orders is as follows:

delete [] Order;

You can confirm this by simply inserting a cout statement in the destructor.

Chad Salinas

Pointer to an Array versus an Array of Pointers

Motivated by Liberty & Jones

Consider the following declarations:

1. Cat FamilyOne[500]
2. Cat * FamilyTwo[500]
3. Cat * FamilyThree = new Cat[500]

FamilyOne is a simple array of 500 Cat objects on the stack — no “new” going on here.

FamilyTwo is an array of 500 pointers to Cat objects, still on the stack.

FamilyThree is a pointer to an array of 500 Cat objects which are on the heap.

Chad Salinas

C++ Pointer Arithmetic

Idea: Take 2 pointers and an array.  Point the 2 pointers at different elements in the array.  Taking the difference between the pointers yields the number of elements separating the 2 pointers.

Motivated by Liberty & Jones

Do you like this signature?  bool GetWord(char * theString, char* word, int& wordOffset)

check edge case of being at the end of string

work:  char * p1, *p2;

p1 = p2 = theString+wordOffset;

trim the leading spaces

determine whether you really have a word

p1 & p2 are at the beginning of same word, so move p2 to the end of the word

get the length by the diff of p2 & p1

…

Chad Salinas

Building an Array of Pointers

Idea: since stack memory is limited and heap memory more abundant, declare objects on the heap.  Thereafter, store only a pointer to the object in the array.

Code Snippet from Liberty Jones’ C++

#include <iostream>

using namespace std;

class Cat

{

public:

Cat() { itsAge = 1; itsWeight = 5; }

~Cat() {}

int GetAge() const { return itsAge; }

int GetWeight() const { return itsWeight; }

void SetAge(int age) { itsAge = age; }

private:

int itsAge;

int itsWeight;

};

int main()

{

Cat * Family[500];

int i;

Cat * pCat;

for (i = 0; i < 500; i++)

{

pCat = new Cat;

pCat->SetAge(2*i + 1);

Family[i] = pCat;

}

for (i = 0; i < 500; i++)

{

cout << “Cat #” << i+1 << “: “;

cout << Family[i]->GetAge() << endl;

}

return 0;

}

Family is declared to hold 500 pointers to Cat objects.  500 Cats are created on the heap.  The pointers to each cat are assigned to the array of pointers vis-a-vis Family[i] = pCat 500 times.

Chad Salinas