?
Solved

Puzzle: loop for recursive problem (Mayankeagle is prefered)

Posted on 2003-03-28
21
Medium Priority
?
471 Views
Last Modified: 2010-04-15
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
Comment
Question by:Kocil
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 5
  • 4
  • +2
21 Comments
 
LVL 10

Expert Comment

by:makerp
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

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

0
 
LVL 5

Author Comment

by:Kocil
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 30

Accepted Solution

by:
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:


void create ( tree * head ) // 'head' must already be allocated memory
{
     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 )
          {
               stack[++top] = head ;
               tracker[top] = i ;
               head = head -> ptr[i] ;
               i = 0 ;

          } // end if

          else
          {
               sum += head -> data ;
               head = stack[top] ;
               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

by:Mayank S
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

by:akshayxx
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

by:Mayank S
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

by:Kocil
ID: 8237741
Wow, it works buddy.

I don't really care about
>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

by:Mayank S
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

by:Kocil
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;
    long sum=head->data;
    if ( head != NULL ) {
      for (i = 0 ; i < head -> count ; i ++ ) {
         sum = sum + total_rec(head->ptr[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 ) {
        stack[++top] = head ;
        tracker[top] = i ;
        head = head -> ptr[i] ;
        i = 0 ;
      } // end if
      else {
        sum += head -> data ;
        head = stack[top] ;
        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)
{
   tree *head;
   int i=0;
   head = malloc(sizeof(tree));
   if (!head) {
      printf("Error creating tree depth = %d\n", depth);
      return NULL;
   }
   head->data = 1;
   head->count = 0;
   if (depth--) {
      while(i<child) {
        head->ptr[i]=create(child, depth);
        if (!head->ptr[i]) break;
        i++;
      }
   }
   head->count = i;
   return head;
}

void delete(tree* head)
{
   int i=0;
   for (i=0; i<head->count; i++) {
      delete(head->ptr[i]);
   }
   free(head);
}

main()
{
   clock_t start;
   tree *head;
   int i;
   long int total;

   /* BC++ at DOS could't create more than this */
   /* please try for more on VC++ windows */
   head = create(2, 10);

   start=clock();
   for (i=0; i<10000; i++) total=total_rec(head);
   printf("TOTAL RECURSIVE = %lu  ", total);
   printf("Time = %lu\n", clock()-start);

   start=clock();
   for (i=0; i<10000; i++) total=total_loop(head);
   printf("TOTAL LOOP      = %lu  ", total);
   printf("Time = %lu\n", clock()-start);

   delete(head);
}

0
 
LVL 30

Expert Comment

by:Mayank S
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

     stack[++top] = head ;

     do
     {
          if ( head != NULL )
          {
               head = head -> left ;

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

          } // end if

          if ( head == NULL )
          {
               head = stack[top--] ;
               sum += head -> data ;
               head = head -> right ;

               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

by:akshayxx
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

by:Mayank S
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

by:Mayank S
ID: 8292039
How about rating it now, Kocil ol' buddy?
0
 
LVL 5

Author Comment

by:Kocil
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

by:akshayxx
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

by:akshayxx
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

by:Mayank S
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

by:Kocil
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

by:Mayank S
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

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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
Suggested Courses

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question