Category Archives: Programming Languages

Lets re-learn Python!


OK: here we go. I learned enough Python to write some, and to follow a lot of Jesse & Co’s at VMware. But I didn’t write all that much, I couldn’t check in anything, because there was not way to  test check-in candidates BEFORE going live. Or, at least, I couldn’t find one. And when I asked for help, I didn’t get what I needed.

But now I’m re-learning, since everyone says they want want proficiency in Python in their new hires. Better brush up on it then. .

So step one.  The canonical program in any Python book goes something like:

print (‘Lesson_1.py with single quote’)
print (2 ** 902)

to show off the easy familiarity Python has with very large numbers.

So I expanded on that. More print statements and if else and elif, Adding a demo of indents being isolated – The block for “if” must be all the same indent, the block for  else need to all be the same. But nothing requires the “if” block to match the “else” block. All they have to be is the same within themselves. Parseable.

Next, since we’re always printing things, what does “print()” return? Not-1, according to the if-then. If we print it, its “None”.  And we can test that it equals “None” (string equals is “==”. It does equal “None”.

But not only does it NOT not equal “none”, you can’t ask that question, without declaring/creating a “none”.  But its not a compile time call. The power of late binding is that nobody has checked “none” (or “NoNe”) until the “==” gets it.

And we get a lovely error:

“what comes back when we print one char
None
no char indent
None = print returned 1 or thereabouts
Traceback (most recent call last):
File “lesson_1.txt”, line 40, in <modul
if none == print(” no char indent”):
NameError: name ‘none’ is not defined”

And now our canonical program has an error, so we can canonically use the “try”, “except”, “finally”  statents.

And if we’re  really lucky, the response will have an error and we’ll get a SECOND TRIP through the error handler!

C:\Users\wabbott\python\Lesson_1>python lesson_1.txt
Lesson_1.py with double quote
Lesson_1.py with single quote
3381084999268257576654974623465706281720622886631177741618948537770712976363039
one char indent
else four char indent
elif six char indent
no char indent
print returned not-1 or thereabouts
what comes back when we print one char indent
None
None == print()
None == print returned 1 or thereabouts
we always do this, but don’t make any mistakes!
Traceback (most recent call last):
File “lesson_1.txt”, line 57, in <module>
if none == print(“none == print()”):
NameError: name ‘none’ is not defined

and there we go.

 

# Lesson_1.py
# picking-up the Python thread again, 5 years later.
# All the recruiters hope I know it, better look into that and perhaps I can find a job.
#

#!/usr/bin/python – ha!

try:

print (“Lesson_1.py with double quote”)
print (‘Lesson_1.py with single quote’)
print (2 ** 902)

# Python uses indentation instead of curly braces to identify blocks. Kind of a nice idea.

if 1:
print( ” one char indent”) # this one prints
else:
print( ” two char indent”)
if 0:
print( ” if three char indent”)
else:
print( ” else four char indent”) # this one prints

 

if 0:
print( ” if five char indent”)
elif 1:
print( ” elif six char indent”) # This one prints
elif 0:
print( ” elif seven char indent”)
elif 1:
print( ” elif eight char indent”)

 

 

if print(“no char indent”):
print(” print returned 1 or thereabouts”)
else:
print(”  print returned not-1 or thereabouts”)

print ( print (” what comes back when we print one char indent”))

 

if (None == print(“None == print()”)):
print(” None == print returned 1 or thereabouts”)
else:
print(” None != print returned not-1 or thereabouts”)

 

if none == print(“none == print()”):
print(” none == print returned 1 or thereabouts”)
else:
print(” none != print returned not-1 or thereabouts”)

 

if NoNe == print(“NoNe == print()”):
print(” NoNe ==44 print returned 1 or thereabouts”)
else:
print(” NoNe != print returned not-1 or thereabouts”)

#  except Argument:
# print(“The argument is>”, Argument, “< ” )

print(“And look, now it fell through!”)

finally:

print(“we always do this, but don’t make any mistakes!”)

# ———-X———-X———-X———-X———-X———-X———-X———-X———-X———-X

Ha! I now have a trivial python program the works interactively! momdad.py:


“””
“””

import os

print “os.listdir(os.getcwd())”
print os.listdir(os.getcwd())

for fname in os.listdir(os.getcwd()):
print fname
text=open(fname).read()
print “text.count( hi mom )”
print text.count(‘hi mom’)

Trending up: Windows7, Agile Methodologies, Scrum, Python. Everything else? Down!


Linked-in are now listing ala-carte qualifications which one can endorse one’s acquaintances on, or be endorsed by them. No surprise, 20 people say I’m good at “hardware”, which is my highest endorsement. What I want to draw your attention to here is that if you hover your pointer over each of the possible qualifications, Linked-in will show you a working definition and the year-to-year trend on people who say they do-have-know-practice-are-qualified-in the specific item.

Not so surprising, people saying they know ‘hardware’ are down year on year… also C, C++, software engineering, Perforce, customer support, regression test, unit test, and so forth. VMware is 0% – neither up nor down over last year.

Agile Methodologies are up, Windows 7 is way-up, Python is up, Scrum is up. The other 44 categories, on my list, not including VMware at 0 and Windows 8 which doesn’t have a year on year trend, are down.

So, among people who list qualifications similar to mine, the majority and growth area are Python users, on Windows 7, employing Scrum and Agile project management methods.

Your choice whether that’s:

a) what everyone wants;

b) what people looking for work think they need;

c) some cross section of professionals on Linked-in.

I think its worth noting in passing, but not worth a lot of study. But it is a curiosity.

An example that pleased me: The difference between an abstract class and an interface, in Java:


Here’s the punch line:

In Java, Prussia can extend (“be a”) one of the super-classes, Holy, Roman or  Empire, but only one. Prussia can implement the other two as interfaces, but only with methods and fields uniquely its own. If Prussia is to be Holy, be Roman and be an Empire, the strictly hierarchical relationship of those three super-classes has to be worked out separately and in detail, in advance. I can only imagine Herr von Bismark would approve.

 

And the whole magilla:
1) What is the difference between an interface and an abstract class?

An abstract class defines data (fields) and member functions but may not, itself, be instantiated. Usually, some of the methods of an abstract class are abstract and expected to be supplied by a sub-class, but some of the methods are defined.  Unless they are final, they can be overridden, and they can always be overloaded. Private parts of an abstract super class, for example, data, are not available to a subclass, so access methods (public or protected) must be used by the subclass. An abstract superclass is “extended” by a subclass. A given subclass may only extend one super-class, but a super-class may extend another super-class, in a hierarchy. (This avoids the complexities/difficulties of multiple inheritance in C++)

An interface is a proper subset of an abstract class, but has a different scope and use. An interface has ONLY abstract member functions and static, final, fields, aka constants. Any subclass has to provide all the variable fields and code which implements an interface. The implementing class cannot override the interface’s member signatures – the signatures are what the interface *is*. It is possible to overload an interface’s signatures, adding or subtracting variables, changing return or variable types, but the overloads do not satisfy the requirements of the interface. The implementing class(s) must contain actual member functions to satisfy all of the signatures in the interface, because there is no default, no code in the interface.  As used above, a given class ‘implements’ an interface, it does not ‘extend’ it. These limitations to an interface allow a given class to implement more than one, which retains most of the utility of multiple inheritance without, as it were, opening Plethora’s bag. (grin)

For example: In Java, Prussia can extend (“be a”) one of the super-classes, Holy, Roman or  Empire, but only one. Prussia can implement the other two as interfaces with methods and fields uniquely its own. If Prussia is to be Holy, be Roman and be an Empire, the strictly hierarchical relationship of those three super-classes has to be worked out separately and in detail, in advance. I can only imagine Herr von Bismark would approve.

Escape (‘\’) your “\” (backslash) characters when Python writes paths for Windows…


When using Python to prepare strings For Windows, always escape ‘\’ your “\” (backslash) characters in a path name. So ‘\\’ everywhere. It looks like a double ‘\’ but the first one is really “escape” and the second character is interpreted as a literal, not, in this case, as ‘escape’…

What am I talking about??

If your Python program will create file path names for Windows computers, you need to be extra thoughtful as you enter string constants for them.

For example, consider the string "blather\pather\gather"
Give that to the Python Interpreter, and it will show you how it is understood by Python:

>>>
>>> "blather\pather\gather"
'blather\\pather\\gather'
>>>

See what happedened to “blather\pather\gather”?
Python put an escape back slash before each of the (presumably) literal back slashes. Its easy to see if you line them up:

"blather\pather\gather"
'blather\\pather\\gather'

The string delimiters have changed too- python gives ‘ and ” the same meaning, defaults to ‘ and requires them to be used in pairs. ” is an empty string, “” is an empty string, ‘” opens a quoted string inside a quoted string. Better not close it backwards: “”” is an empty string. “‘”‘ is missing a close “.

So far, so good. You might think Python will understand back slashes in things you identify as strings and respect them. That’s nice.

Change the string to
"blather\rather\ather"
>>>"blather\rather\x07ther"

What’s that?? Turns out that Python recognizes “\r” as (carriage return), “\n” a newline and “\t” as a tab. And \a as (control)a, with is slightly startling. But not \G or \g as “bell”…

So they’re compound characters, and they get issued without escapes being added. Why? I don’t know. But I do know that putting an excape backslash before the delimiter backslash results in the text being left alone, and written out exactly the same. And when it goes to Windows, Windows strips off the first backslash and correctly interprets the second one.

Here’s an advantage for Python, as my friend James points out. You can just look at what it does and how it sees things. The realization I’m reporting started wth a Python script trying to call a Windows .bat script… it worked well for some .bat scripts and didn’t work for others. ?!?!?!

Searching for apples and oranges, using grep.


Not using grep? Its a step up from sorting and cutting and pasting in spreadsheets. You will feel, briefly, omniscient, when you use it to solve some problem that’s been bugging you. Here’s my latest:

You care about two keywords in a file- apples and oranges, and you also care about about their relative positions, for whatever reason. So grepping for each, separately, is nice, but you’d really like to grep for one OR the other.

Did I mention this was grep?

grep -i ‘apple\|orange’ *filename.ext*

The -i makes it case-insensitive, just like you’d want on a first pass. The “|” vertical bar is a familiar OR operator, and the only tricky parts are to a) put the whole thing in a single set of single quotes- the two words and the operator are a single syntactic unit, and b) use a back-slash to mark the vertical bar as an operator and not just a literal vertical bar.

I used apple and orange in the title because they are canonically “unrelated” things, but where this technique is really useful is when the unrelated things are in orthagonal kinds: fruits and deserts. If you’ve got your recipes filed or a cookbook on line, grep -i ‘pie\|apple’ will produce all the refernces to either. Pies involving apples will be found where ‘apple’ has ‘pie’ both above and below… As a human, you have a right to do that last bit in your head, the sorting out that we gatherer-hunters are bred for.

The Story of Mel


If you’ve never had the pleasure, or would like to enjoy it again, you can find this delightful, hacked-into-free-verse, ode to Real Programmers and their mysterious ways:

http://www.cs.utah.edu/~elb/folklore/mel.html

Besides Tracy Kidder’s “The Soul of a New Machine”, this is the only work of art that I know of to capture a big piece of the joy, sorrow, transcendence and goofy humor of engineering as a profession. “The Cuckoo’s Egg” by Cliff Stoll touches on some of these, but its not about engineering, in the small sense. Not about hand-assembling machine language so that each instruction was physically located just a bit further along on the drum memory, (instruction skew, not simply sector skew…). Well, I’ll let Mr. Ed Nather tell the story: see above link.

Recursion III, using Java


Here’s a Java example of the classic recursion/tree/web traversal. Note that this uses an array of other nodes, not just Left and Right, so you can make n-link webs as well as proper trees using this example.

The method interMed() is used to avoid having to make the data structures static- there is much I have yet to learn about Java! But I can manage this, and that feels pretty good!

/*
recurse.java

Recursive tree/web traversal, in Java. No explicit pointers, so I state that
the array of pointers to nodes is an array of nodes, and treat it as such.
Is it really pointers if I believe it is but can't see them? Its like String
Theory...

Original 11:58am 4/21 Bill4

*/

import java.util.ArrayList;

public class recurse {

public class node { String name; ArrayList kids; };
public class leveledName { String name; int level; };

ArrayList nLs = new ArrayList ();

public void recur ( node n, int level ) {

// System.out.println( "recur " + n + " level " + level );
leveledName lN = new leveledName();
lN.name = n.name;
lN.level= level;
nLs.add( lN );

for ( int i = 0; i < n.kids.size(); i++ ) { // better way to do this?

recur( n.kids.get(i), level + 1 );

} // for int i...

} // recur function

public void interMed() {

node Q = new node(); Q.name = "Q";
Q.kids = new ArrayList ();
// System.out.println( Q );

node S = new node(); S.name = "S";
S.kids = new ArrayList ();
// System.out.println( S );

node T = new node(); T.name = "T";
T.kids = new ArrayList ();
// System.out.println( T );

node N = new node(); N.name = "N";
N.kids = new ArrayList (); N.kids.add(Q);
// System.out.println( N );

node P = new node(); P.name = "P";
P.kids = new ArrayList (); P.kids.add(S); P.kids.add(T);
// System.out.println( P );

node M = new node(); M.name="M";
M.kids = new ArrayList (); M.kids.add(N); M.kids.add(P);
// System.out.println( M );

recur( M, 0 );

int maxLevel = 0;
for ( int i = 0; i maxLevel) {
maxLevel = ((nLs.get(i)).level );
} // if ...
} // for ...

for (int j = maxLevel; j > -1; j-- ) {
// System.out.println( "j " + j );
for ( int i = 0; i < nLs.size(); i++ ) {
// System.out.println( "j " + j + " i " + i );
if ( j == (nLs.get(i)).level ) {
System.out.printf( "%s %d \n", (nLs.get(i)).name,
(nLs.get(i)).level );
}
} // for i...
} // for j...

} // fn interMed

public static void main ( String args[] ) {

recurse r = new recurse();
r.interMed();

} // main

} // class recurse

Recursion II, K&R C, worked out in advance


Earlier I posted the C++ solution to a tree/web traversal programming problem. Here’s the C solution, including a vector-like array for pointers to children, so one doesn’t have to hard code left, right, etc. In this case Max Children is 5 but it can be any number.  A sample output is included below

/* recursion.C */
/* Follow-up to _ recursion problem, web prowling question at _  */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)

(3 level b tree, M has two kids, N and P, and N has two kids, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <stdio.h>
#include <stdlib.h>

#define MAX_NAME_N_LEVEL 1000
#define MAX_KIDS  5

/* Structure in which the input data arrives: */

struct node {
char name;  struct node *(kids[MAX_KIDS]);
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
char name;   int level;
};

/* Global scope variables for putting struct node + name data, as discovered in recursive part. */

struct nameNLevel* nsNLs[ MAX_NAME_N_LEVEL ];
int nmLvlCount = 0;

/*
* Synopsis:  void recur( int level, struct node* n ) {
* args:
*    int level
*    struct node* n
* returns: void, BUT puts a record into nsNLs[] and increments nmLvlCount.
* The record contins a node name and the level it was found at.
* Apr 5, 2011  Bill Abbott
*/

void recur( int level, struct node* n ) {
/* first make the new record in the list of names and levels */

struct nameNLevel* thisNmNLvl = (struct nameNLevel*) malloc( sizeof( struct nameNLevel));    /* allocate name string & level num struct */
if (0 == thisNmNLvl ) { /* allocation failed! */
printf(“Memory allocation failed at level %d, struct node %s, go ahead and crash!\n”, level, n->name );
}

thisNmNLvl->level = level;            /* fill in level, */
if ( n != 0 ) thisNmNLvl->name = n->name;             /* 1 char name… */
nsNLs[ nmLvlCount++ ] = thisNmNLvl;

printf(“\n”);
printf(“recur level: %d    n: 0x%x   name: %c\n”, level,  n, n->name );
/*
printf(“(long)*(n > kids)  :  0X%x \n”, (long)*(n->kids) );
printf(“(long)(n > kids[0]):  0X%x \n”, (long)(n->kids[0]) );
*/
/* those two should be the same… */

if ( 0 != n->kids ) {  /* this pointer should always have an array where it points, but just in case… */

int j;
for (j=0; j<3; j++ ) {
printf(” (n > kids[%d]) = 0x%x  “, j, (n->kids[j]) );
if ( n->kids[j] ) { printf(”   >name = %c\n”, (n->kids[j])->name ); }
else { printf( “\n” ); }
}   /* ha! This was the hardest part… */
}

int i;
/* now look for any child nodes an call recursivly for them… */
for ( i = 0; n->kids[i] != 0; i++ ) {
recur(level+1,  n->kids[i]);
} /* for int it… */

} /* recur */

/*
* Synopsis: void passThrough( struct node* n )
* args:
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( struct node* n ) {

int i;
for( i = 0; i< MAX_NAME_N_LEVEL; i++ ) { /* not strictly required…*/
nsNLs[ i ] = 0;  // set ’em all to null to start with.
} /* for i… */

int level = 0;
nmLvlCount = 0;

recur( level, n );

int maxLevel = 0;
for (i = 0; i < nmLvlCount; i++ ) {
if ( nsNLs[ i ]->level > maxLevel ) {
maxLevel = nsNLs[ i ]->level;
} /* if…*/
} /* for int i… */

/*    printf(“\nlevel  %d    nmLvlCount  %d     maxLevel %d \n”, level, nmLvlCount, maxLevel ); */

int lvl;
printf(“\n”);
for ( lvl = maxLevel; lvl >= 0; lvl– ) {  // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%c, “,  nsNLs[i]->name );
}
}
} /* for int i… */
printf(“\n”);

for ( lvl = maxLevel; lvl >= 0; lvl– ) {  // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%d, “, nsNLs[i]->level );
}
}
} /* for int i… */
printf(“\n”);

} /* passThrough */

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Apr 7, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two kids, N and P, and
*    N has two kids, Q and S.
*        Q has no kids
*        S has no kids
*    P has one child – T.
*        T has no kids
*/

char nameIt[] =”malloc “;
char theRest[] = ” failed. Out of memory\n”;

struct node* T = malloc( sizeof(struct node));
if ( 0 == T ) { printf(“%s T %s”, nameIt, theRest ); return( 0 ); }
T->name = ‘T’;
T->kids[MAX_KIDS] = (struct node*) malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == T->kids ) { printf(“%s T->kids %s”, nameIt, theRest); return( 0 ); }
T->kids[0] = (void*) 0;
T->kids[1] = (void*) 0;
T->kids[2] = (void*) 0;

/*
printf(“\n”);
printf(“(long)(T > kids) = 0X%x   \n”,  (long)*(T->kids) );
if ( (T->kids[0]))  printf(“*(T > kids[0]) = %c\n”,   *(T->kids[0]) );
if ( (T->kids[0]))  printf(“( (T > kids[0]) >name = 0x%x  %c\n”,   (T->kids[0])->name, (T->kids[0])->name );
if ( (T->kids[1]))  printf(“( (T > kids[1]) >name = 0x%x  %c\n”,   (T->kids[1])->name, (T->kids[1])->name );
if ( (T->kids[2]))  printf(“( (T > kids[2]) = 0x%x\n”,   (T->kids[2]) );
*/

struct node* S = malloc( sizeof(struct node));
if ( 0 == S ) { printf(“%s S %s”, nameIt, theRest ); return( 0 ); }
S->name = ‘S’;
S->kids[MAX_KIDS] = malloc( sizeof( struct node*) * MAX_KIDS);
if ( 0 == S->kids ) { printf(“%s S->kids %s”, nameIt, theRest); return( 0 ); }
S->kids[0] = (void*) 0;
S->kids[1] = (void*) 0;
S->kids[2] = (void*) 0;

struct node* Q = malloc( sizeof(struct node));
if ( 0 == Q ) { printf(“%s Q %s”, nameIt, theRest ); return( 0 ); }
Q->name = ‘Q’;
*(Q->kids) = malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == Q->kids ) { printf(“%s Q->kids %s”, nameIt, theRest); return( 0 ); }
Q->kids[0] = (void*) 0;
Q->kids[1] = (void*) 0;
Q->kids[2] = (void*) 0;

struct node* P = malloc( sizeof(struct node));
if ( 0 == P ) { printf(“%s P %s”, nameIt, theRest ); return( 0 ); }
P->name = ‘P’;
P->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == P->kids ) { printf(“%s P->kids %s”, nameIt, theRest); return( 0 ); }
P->kids[0] = T;
P->kids[1] = (void*) 0;
P->kids[2] = (void*) 0;

struct node* N = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
N->name = ‘N’;
N->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == N->kids ) { printf(“%s N->kids %s”, nameIt, theRest); return( 0 ); }
N->kids[0] = Q;
N->kids[1] = S;
N->kids[2] = (void*) 0;

struct node* M  = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
M->name = ‘M’;
M->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == M->kids ) { printf(“%s M->kids %s”, nameIt, theRest); return( 0 ); }
M->kids[0] = N;
M->kids[1] = P;
M->kids[2] = (void*) 0;

/*  printf(“\n”);
printf(“(long)(M > kids) = 0X%x   \n”,  (long)*(M->kids) );
printf(“*(M > kids[0]) = %c\n”,   *(M->kids[0]) );
printf(“( (M > kids[0]) >name = 0x%x\n”,   (M->kids[0])->name );
printf(“( (M > kids[1]) >name = 0x%x\n”,   (M->kids[1])->name );
printf(“( (M > kids[2]) = 0x%x\n”,   (M->kids[2]) );
*/

passThrough( M );

return( 1 );

} // main…

Macintosh-6:interview Bill4$ cc recursion.c
Macintosh-6:interview Bill4$ a.out

recur level: 0    n: 0x100260   name: M
(n > kids[0]) = 0x100220     >name = N
(n > kids[1]) = 0x1001e0     >name = P
(n > kids[2]) = 0x0

recur level: 1    n: 0x100220   name: N
(n > kids[0]) = 0x1001a0     >name = Q
(n > kids[1]) = 0x100160     >name = S
(n > kids[2]) = 0x0

recur level: 2    n: 0x1001a0   name: Q
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 2    n: 0x100160   name: S
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 1    n: 0x1001e0   name: P
(n > kids[0]) = 0x100120     >name = T
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 2    n: 0x100120   name: T
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

Q, S, T, N, P, M,
2, 2, 2, 1, 1, 0,
Macintosh-6:interview Bill4$

Recursion, working it out in advance


In a recent pair of interviews, I was asked tree data structure questions, and I flubbed the first one. Hacking at a function that received a pointer to a node and that I needed to use as the launching point for recursion, not the recursive bit itself. Not pretty. NEXT time, I managed to gather up my wits, with a bit of help from my interviewer, Jim Gill, I managed to thread the needle and there it was, a recursive operation that worked. Sho-‘nuf!  That original is at the bottom of this post- a complete, working version, follows this introduction. Its about 180 lines, with a lot of white space.

And here’s the deal. You can’t make  a sensible recursive routine by simply getting the pointer and recalling that top level routine. YES recursion needs something that takes a pointer to node, and yes,  you call it with a child of the original node. But there’s more to it. A non-recursive superstructure which supports a recursive heart.

So here’s a complete, working, version, that compiles and runs using “gcc” on Mac OS 10.5.8. It takes a bit more than what I started with. “C” and other versions will follow, as separate postings.

Macintosh-6:interview Bill4$ cat recursion_v.cpp
/* recursion_v.cpp */
/* Follow-up to ___ recursion problem with Jim Gill, web prowling question at ____ */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <iostream>
#include <vector>

/* Structure in which the input data arrives: */

struct node {
std::vector <node*> children;  std::string name;
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
std::string name;   int level;
};

/*
* Synopsis: void recur( node* n, int level, std::vector* nsNLs )
* args:
* node*    n     this node, which has a name, may have children
* int        level    number of steps down the tree
* std::vector    nsNLs   pointer to the vector of node-name, level structs we’ll want to report
* returns:
* no return value. Node name and level are put into the vector of nameLevel structs.
* Mar 27, 2011  Bill Abbott
*/

void recur( node* n, int level, std::vector <nameNLevel>* nsNLs ){

/* To collect additions, nsNLs vector must be passed as a pointer! */
/* Unlike an array in C, an std::vector isn’t passed as a pointer automatically! */
nameNLevel* nNL = new nameNLevel;
nNL->name = n->name;
nNL->level = level;
nsNLs->push_back( *nNL );

int vecIdx = nsNLs->size() – 1;

//    std::cout << nsNLs->size() << ”  ” << vecIdx << ”    “;
std::cout << (*nsNLs)[ vecIdx ].level << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.size() << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.c_str() << ”    “;

std::cout << (nsNLs->back()).name << ”  ” << (nsNLs->back()).level << ”  ” << n->name << ”  ” << level << ”  “;
std::cout << nsNLs->size() << ”  ” ;
std::cout << n->children.size() << ”  ” << (0 != n->children.size()) << “\n”;
if ( 0 != n->children.size()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.size()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs ); /* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

} /* recur *

/*
* Synopsis: void passThrough( node* n )
* args:
* node*    n     this node, which has a name, may have children
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( node* n ) {
std::vector namesNLevels;
int level = 0;

recur( n, level, &namesNLevels );

std::cout<< namesNLevels.size()  << ”  ” << “\n”;

int maxLevel = 0;
for (int i=0; i < namesNLevels.size(); i++ ) {
std::cout<< maxLevel << ”  ” << i << “\n”;
if (namesNLevels[i].level > maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=maxLevel; level >= 0; level–){
for (int i=0; i < namesNLevels.size(); i++ ) {
if (namesNLevels[i].level == level){
std::cout << namesNLevels[i].name <<  ” “;
} /* if (namesNLevels…) */
} /* for i */
} /* for level */

printf( “\n”);

}

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two children, N and P, and
*    N has two children, Q and S.
*        Q has no children
*        S has no children
*    P has one child – T.
*        T has no children
*/

node* T = new node;
T->children.clear();
T->name = “T”;

node* S = new node;
S->children.clear();
S->name = “S”;

node* Q = new node;
Q->children.clear();
Q->name = “Q”;

node* P = new node;
P->children.push_back(T);
P->name = “P”;

node* N = new node;
N->children.push_back(Q);
N->children.push_back(S);
N->name = “N”;

node* M = new node;
M->children.push_back(N);
M->children.push_back(P);
M->name = “M”;

passThrough( M );

return( 1 );

————- Example output, with my debug couts—————-

Macintosh-6:interview Bill4$ c++ recursion_v.cpp
Macintosh-6:interview Bill4$ a.out
0  M  1  M    M  0  M  0  1  2  1
1  N  1  N    N  1  N  1  2  2  1
2  Q  1  Q    Q  2  Q  2  3  0  0
2  S  1  S    S  2  S  2  4  0  0
1  P  1  P    P  1  P  1  5  1  1
2  T  1  T    T  2  T  2  6  0  0
6
0  0
0  1
1  2
2  3
2  4
2  5
Q S T N P M
Macintosh-6:interview Bill4$

————————– Here’s how this started:——————–

Ok- it was whiteboard code and didn’t compile. I’m working on that. Staring with std::vector blahblah  which seems like some really kewl Java/C++ library good stuff. What Kernighan and Ritchie were hoping for.

input:
(M)
|     \
(N) (P)
|     \    \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.

output:
Q, S, T, N, P, M

typedef struct node {
std::vector <node*> children;  std::string name;
}

typedef nameNLevel {
std::string name;   std::int level;
}

void passThrough( node* n ) {
std::Array namesNLevels;
int level = 0;

recur( n, level, namesNLevels );

int maxLevel = 0;

for (int i=0; i
if (namesNLevels[i].leve l> maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=0; level =<maxLevel; level++){
for (i=0; i<
if (atoi(namesNLevels[i].name) == level){  printf( “%s “, namesNLevels[i].name } /* longer but more robust */
} /* for i */
} /* for level */

printf( “\n”);

}

void recur( node* n, integer level, std::Array nsNLs ){
/* its an array, gets passes as a pointer anyhow */
nsNLs.pushback( new nameNLevel( n->name, level));

if ( 0 != n->children.count()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.count()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs );
/* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

}

A nice page at IBM regarding recursion:

http://www.ibm.com/developerworks/linux/library/l-recurs.html#

Good stuff!