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!