Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Puzzle: loop for recursive problem (Mayankeagle is prefered)

Posted on 2003-03-28
Medium Priority
482 Views
The original question is from :
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20566400.html

> The title is like this: "A" is the sales manager and he has 2 downline,
> which is "B" and "C". "B" has 2 downline,which is "D" &"E"...
> So..the question is ..I want to know the total sales result of "A" downline,
> which is B,C,D and E...but can't used for loop because it will be very messy
> if there are lots of downline...

My curiosity is ... how to solve it in the very messy way:
* many direct downlines, not only 2.
* use loop, can't use recursive here !

0
Question by:Kocil
• 10
• 5
• 4
• +2

LVL 10

Expert Comment

ID: 8229982
when you have an unknown depth then recursion is almost always the easiest way to solve the problem.

each member of staff in your case could be represented by the following structure

struct _staff
{
char *name;
int sales_total;
int number_of_sub_staff;
struct _staft *array_sub_staff;
}

recursion here would be very easy

int get_sales_total(struct _staff *staff)
{
int retval = staff->sales_total;
for(int i=0;i<staff->number_of_sub_staff;i++)
retval += get_sales_total(staff->array_of_sub_staff[i]);
return retval;
}

now how you populate the tree of staff is up to you...

may i suggest that if you can you solve this problem in C++, you can then make use of classes to abstract the staff and use teh STL for your arrays etc..

if you use c then you will need to use realloc to rezise the array_of_sub_staff

Paul
0

LVL 22

Expert Comment

ID: 8230382
See Knuth, Volume 1 I think, he covers traversing trees, complete with algorithms.

0

LVL 5

Author Comment

ID: 8233684
For makerp, thanks.
But I'm asking a NON recursive algorithm, because it have been proposed on
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20566400.html

My intention here is to discuss other alternatives algorithms that may solve that problem more efficiently than recursive.

Back when I was working with prolog, recursive is the most used algorithm. However, the manual said that we have to try to make a tail-recursion, because tail-recursion can be computed more efficiently as a loop. I tested that suggestion and yes, tail recursion was about 5 times faster than normal recursion. I accepted that result, without exactly know what happen inside the prolog engine.

So actually, what I want to know is, how to implement  tail-recursion in C. It should be a loop, like the prolog manual said, and not recursive.

For grg99, I'm sorry I don't have Knuth.
(don't tell my proffessor please. She will really angry to know one of his student does not have the old 'bible'). I will appreciate if you post the algorithm here.

Thanks.

0

LVL 30

Accepted Solution

Mayank S earned 300 total points
ID: 8236877
Hi Kocil, ol' buddy,

Let's say the structure is of the following format:

#define MAX 100

struct tree
{
int data ;
int count ;
tree * ptr[MAX] ;

} ;

I am assuming that the 'data' field holds the amount to be summed.

You can use the following functions to create and display the data-structure:

{
cout << "\n Enter data: " ;
cin >> head -> data ;

cout << "\n How many children does " << head -> data << " have: " ;
cin >> head -> count ;

if ( head -> count > 0 )
{
for ( int i = 0 ; i < head -> count ; i ++ )
{
head -> ptr[i] = new tree ;
create ( head -> ptr[i] ) ;

} // end for

} // end else

} // end of create ()

void display ( tree * head )
{
if ( head != NULL )
{
cout << head -> data << endl ;

for ( int i = 0 ; i < head -> count ; i ++ )
display ( head -> ptr[i] ) ; // end for

} // end if

} // end of display ()

These were, of course, recursive functions. You can call them from main () as:

tree * root = new tree ;
create ( root ) ;
display ( root ) ;

Now, the non-recursive function to add up all the data at and below a node:

int total ( tree * head )
{
tree * stack[100] ;
int top = -1, sum = 0, i = 0, tracker[100] ;

if ( head == NULL )
return 0 ; // end if

else
sum = head -> data ; // end else

do
{
if ( i < head -> count )
{
tracker[top] = i ;
i = 0 ;

} // end if

else
{
sum += head -> data ;
i = tracker[top--] + 1 ;

} // end else

} while ( top != -1 || i < head -> count ) ;

return sum ;

} // end of total ()

You can call it as:

cout << total ( root ) ;

You can also test the function for other cases as:

cout << total ( root -> ptr[0] ) ;

It should give the sum of all the values at and below that node.

Mayank.

0

LVL 30

Expert Comment

ID: 8236936
Create the tree entering data in the following sequence:

1
4
2
3
6
0
7
0
8
0
3
1
9
2
12
0
13
0
4
2
10
0
11
0
5
0

And see if it gives 91 as the total or not.

[Root: 1
1 has 4 children: 2, 3, 4, 5
2 has 3 children: 6, 7, 8
3 has 1 child: 9
9 has 2 children: 12, 13
4 has 2 children: 10, 11
5, 6, 7, 8, 12, 13, 10 and 11 have no children.]

Mayank.
0

LVL 8

Expert Comment

ID: 8237127
>>>#define MAX 100

>>struct tree
>>{
>>    int data ;
>>    int count ;
>>    tree * ptr[MAX] ;

>>} ;

i will be reluctant to use
>>>tree *ptr[MAX];
since for each node .. even if the potential children are 2 or three .. u still allocate MAX numbers of "tree *ptr",

so u better have a linked list there.. (preferrably doubly linked list) .. OR some simple growable hashtable.
0

LVL 30

Expert Comment

ID: 8237183
I agree with that, Akshay. I just showed a simple demo on how to implement the non-recursive algo. Alternatively, you can use a dynamically allocated array (then only the implementation of the create () will differ, and the total () remains the same).

Mayank.
0

LVL 5

Author Comment

ID: 8237741
Wow, it works buddy.

>struct tree
>{
>    tree * ptr[MAX] ;
>}

It's a matter of implementation.

But this is what I'm interested for.

int total ( tree * head )
{    tree * stack[100] ;
int top = -1, sum = 0, i = 0, tracker[100];
...
}

So, we need to emulate stack here.
Nice one. It answers my curiosity.
Hmm... do you think we can remove the tracker[100] ?

0

LVL 30

Expert Comment

ID: 8237934
Not at all. Its very important. Its also kind of a stack - a stack for storing integer values. The stack[] array is supposed to hold the address of a node, and the tracker[] array is supposed to hold the index of the child (in 'ptr[]') which is being traversed currently. Once we finish this sub-tree, we get back to this node and also take this index value from the tracker[] array, increment it by one and go to the next sub-tree (in 'ptr[]'), so that we don't end up traversing an already traversed sub-tree again.

Mayank.
0

LVL 5

Author Comment

ID: 8239720
I test recursive vs loop :
TOTAL RECURSIVE = 2047  Time = 121
TOTAL RECURSIVE = 2047  Time = 90

Loop is faster, but only by 25%;

I'm still lookin to remove tracker[100],
because the recursive function is called only by ptr* head, so logically, the emulate stack should only ptr* stack too.

The code for testing

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

#define MAX 50

typedef struct tree
{
int data ;
int count ;
struct tree *ptr[50];
} tree;

/* recursive algorithm */
long total_rec( tree * head )
{
int i;
if ( head != NULL ) {
for (i = 0 ; i < head -> count ; i ++ ) {
}
}
return sum;
}

/* loop algorithm */
long total_loop ( tree * head )
{
tree * stack[100] ;
int top = -1, sum = 0, i = 0, tracker[100] ;

if ( head == NULL )  return 0 ; // end if
else sum = head -> data ; // end else

do {
if ( i < head -> count ) {
tracker[top] = i ;
i = 0 ;
} // end if
else {
sum += head -> data ;
i = tracker[top--] + 1 ;
} // end else
} while ( top != -1 || i < head -> count ) ;
return sum ;
}

/* simulate to create tree childxdepth */
tree* create(int child, int depth)
{
int i=0;
printf("Error creating tree depth = %d\n", depth);
return NULL;
}
if (depth--) {
while(i<child) {
i++;
}
}
}

{
int i=0;
}
}

main()
{
clock_t start;
int i;
long int total;

/* BC++ at DOS could't create more than this */
/* please try for more on VC++ windows */

start=clock();
printf("TOTAL RECURSIVE = %lu  ", total);
printf("Time = %lu\n", clock()-start);

start=clock();
printf("TOTAL LOOP      = %lu  ", total);
printf("Time = %lu\n", clock()-start);

}

0

LVL 30

Expert Comment

ID: 8243269
>> TOTAL RECURSIVE = 2047  Time = 121
>> TOTAL RECURSIVE = 2047  Time = 90

You mean:

TOTAL RECURSIVE = 2047  Time = 121
TOTAL LOOP = 2047  Time = 90

>> please try for more on VC++ windows

Sorry, buddy. Even I don't have VC++. Actually, I work more on Java and its been a long time since I worked on C/C++, that's why I didn't bother to install VC.

Actually, there will always be a slightly better performance in iteration (looping) than in recursion, though both use a stack (recursion uses the system stack, whereas in iteration, we make our own stack). The reason for this is that in our iteration, there is no extra function-call, which is a significant advantage as opposed to recursion, because in recursion, there are so many function calls. In our iteration method, we are only pushing one address on to the stack (along with an integer too in this case). In recursion, extra function calls involve creating and pushing an entire activation record of a function on the stack, saving previous register values, variables, return address, etc. Then when a recursive call completes, it pops off the entireactivation record off the stack, then reloads registers and the program counter, etc.

However, like you said that there is only a 25% performance boost in looping. Well, if it was a binary tree, then the performance might have been even better. Here, note that you have put (and I guess, there's no better way) a loop in your recursive function too, as:

>> for (i = 0 ; i < head -> count ; i ++ ) {
>>   sum = sum + total_rec(head->ptr[i]);

Whereas in our non-recursive method, we have used two stacks, one for storing the address of the node, and the other for storing the value of 'i' (which is why I say that the tracker[] array is needed). If we were using simply a binary tree, then we could've slightly modified the algorithm as:

int total ( tree * head )
{
tree * stack[100] ;
int top = -1, sum = 0 ;

if ( head == NULL )
return 0 ; // end if

do
{
if ( head != NULL )
{

if ( head != NULL )
stack[++top] = head ; // end nested if

} // end if

if ( head == NULL )
{
sum += head -> data ;

if ( head != NULL )
stack[++top] = head ; // end nested if

} // end if

} while ( top != -1 ) ; // end do-while

return sum ;

} // end of total ()

which should've given better performance than its recursive counterpart, I guess.

Mayank.
0

LVL 8

Expert Comment

ID: 8250723
since solution has already been suggested .. so i m just playing with words

mayaneagle:
>>>there will always be a slightly better performance in iteration (looping) than in recursion

you should be careful while making such definitive statement.. performance is pretty generic term .. so a lot  depends on performance criterias..and environment also..
also no one knows if someone comes up with some computational procedure more favorable for recursive algorithms than for iterative(loop) ones..
:)
0

LVL 30

Expert Comment

ID: 8250968
>> you should be careful while making such definitive statement.. performance is pretty generic term

Yeah! I agree.... I should've said - "under most circumstances". Its just that so many function calls will result in extra overhead.

Thanks & cheers,

Mayank.
0

LVL 30

Expert Comment

ID: 8292039
How about rating it now, Kocil ol' buddy?
0

LVL 5

Author Comment

ID: 8295152
I have been trying to solve it by using only tree* stack[].
Still no luck :)

How about 250 points for that ?
(I get 2000 QPs to spent each months now :)

0

LVL 8

Expert Comment

ID: 8295873
ohh so u mean its still open .. ok i'll give it a try when i m free.. 250 points for freetime isnt bad :)...
0

LVL 8

Expert Comment

ID: 8296085
ok here is the hint, simple tree data structure will not solve the problem,
Am i allowed to modify the datastructure?.. then i have more than one solutions.
0

LVL 30

Expert Comment

ID: 8297053
>> I have been trying to solve it by using only tree* stack[].

You won't be able to.... you need a different data structure like Akshay said.. huh! My project-deadlines are so close, but anyways, I'll try..
0

LVL 5

Author Comment

ID: 8298005
Data structure is as simple as this.

// count = number of direct children
#define MAX 100
struct tree
{
int data ;
int count ;
tree * ptr[MAX] ;
} ;
or

// NULL terminated the children
#define MAX 100
struct tree
{
int data ;
tree * ptr[MAX+1] ;
} ;

I nearly got the solution by using the second data structure. But something still missing ....

0

LVL 30

Expert Comment

ID: 8298632
>> I get 2000 QPs to spent each months now

You will, if you have a minimum of 10,000 expert-points and score a minimum of 3,000 every month. Its their way of keeping their 'valuable' experts happy :-)

As for the second data structure, can you post your code so that we can see it, buddy....
0

LVL 30

Expert Comment

ID: 8306392
Hey! You're in the top 15 C programmers now... good going!
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ouâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
###### Suggested Courses
Course of the Month12 days, 1 hour left to enroll