440,262 Members | 1,125 Online
Need help? Post your question and get tips & solutions from a community of 440,262 IT Pros & Developers. It's quick & easy.

# Translation from recursive to iterative

 P: n/a Due to a lack of resources, I have to translate the following recursive function in its iterative form. It's a kind of dichotomic search. void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { char ret; //ping over a range of addresses (all slaves with uid in the range from start_uid to end_uid will reply) ret = PingSlave(start_uid,end_uid); if (start_uid == end_uid) //single item { if (ret == VALID_PING_REPLY) AddUidToSlaveList(start_uid); return; } if (ret == VALID_PING_REPLY) { SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 ); //left subtree SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right subtree } } Any help will be greatly appreciated! :-) Regards, Marco Nov 14 '05 #1
14 Replies

 P: n/a BQ wrote: Due to a lack of resources, I have to translate the following recursive function in its iterative form. It's a kind of dichotomic search. void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { char ret; //ping over a range of addresses (all slaves with uid in the range from start_uid to end_uid will reply) ret = PingSlave(start_uid,end_uid); if (start_uid == end_uid) //single item { if (ret == VALID_PING_REPLY) AddUidToSlaveList(start_uid); return; } if (ret == VALID_PING_REPLY) { SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 ); //left subtree SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right subtree [ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good idea. ] } } First thought: get rid of the premature optimisation, get rid of the unnecessary object (yes, I do see the irony): void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) { if (start_uid == end_uid) { AddUidToSlaveList(start_uid); return; } SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1); SearchSlaves((start_uid+end_uid+1)/2, end_uid); } } Second thought: while this algorithm is efficient if slaves are very sparse, or relatively sparse and clustered within the range, this is probably an efficient algorithm. Every slave is pinged several times, though (log2(end_uid-start_uid) times, circa), so if there are many slaves, this is not efficient. Nor is it optimal if there are a reasonable number of slaves peppered through the range. If you suspect one of those may be the case, a straightforward linear search may beat this algorithm. In fact, if PingSlave uses the obvious, naive algorithm for searching its range, this already _is_ a linear search - several times over. One other possibility would be to improve PingSlave's efficiency, perhaps by giving it a (resettable) memory. Richard Nov 14 '05 #2

 P: n/a Richard Bos wrote: [ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good idea. ] ehr, sorry.... :-) First thought: get rid of the premature optimisation, get rid of the unnecessary object (yes, I do see the irony): void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) { if (start_uid == end_uid) { AddUidToSlaveList(start_uid); return; } SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1); SearchSlaves((start_uid+end_uid+1)/2, end_uid); } } Second thought: while this algorithm is efficient if slaves are very sparse, -- and this is the case: max.20/30 'slaves', sparse over a range 2^16 wide or relatively sparse and clustered within the range, this is probably an efficient algorithm. Every slave is pinged several times, though (log2(end_uid-start_uid) times, circa), so if there are many slaves, this is not efficient. Nor is it optimal if there are a reasonable number of slaves peppered through the range. If you suspect one of those may be the case, a straightforward linear search may beat this algorithm. in my situation, a straightforward linear search can't be made. Every ping has a 150ms timeout that can't be reduced, and the searchspace is very large. In fact, if PingSlave uses the obvious, naive algorithm for searching its range, this already _is_ a linear search - several times over. Slaves answer to the ping if their uid is start_uid<= uid <= end_uid. So searching 10/20 slaves requires about 2-3 seconds at most Anyway, this code is compiled against a microprocessor with very limited resources and I have a problem with stack that pushes me toward searching an iterative version of this algorithm: I can make at most 32 subroutine calls, and SearchSlave calls itself at least 16 times in a 2^16 space. Since SearchSlave is not at level 0, I sometime obtain a stack overflow. By the way, theory assures that a recursive algorithm can always be rewritten in an iterative way. If anyone has an idea... Regards, Marco Nov 14 '05 #3

 P: n/a BQ wrote: Due to a lack of resources, I have to translate the following recursive function in its iterative form. It's a kind of dichotomic search. void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { char ret; //ping over a range of addresses (all slaves with uid in the range from start_uid to end_uid will reply) ret = PingSlave(start_uid,end_uid); if (start_uid == end_uid) //single item { if (ret == VALID_PING_REPLY) AddUidToSlaveList(start_uid); return; } if (ret == VALID_PING_REPLY) { SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 ); //left subtree SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right subtree } } Any help will be greatly appreciated! :-) Regards, Marco You might start by making it easy for people to help you. 8 char indents are excessive, // comments don't survive line wrapping well, and any linelength over about 72 is likely to cause a problem on newsgroups. Do not use tabs, use spaces. Include dummy functions for the undefined things, so that people can compile it immediately. As it is the SearchSlaves operation seems singularly useless, since it returns nothing. -- "I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare Nov 14 '05 #4

 P: n/a CBFalconer wrote: You might start by making it easy for people to help you. 8 char indents are excessive, // comments don't survive line wrapping well, and any linelength over about 72 is likely to cause a problem on newsgroups. Do not use tabs, use spaces. Include dummy functions for the undefined things, so that people can compile it immediately. As it is the SearchSlaves operation seems singularly useless, since it returns nothing. Thanks CBFalconer, I'll keep it in mind when I'll write a post next time. Regards, Marco Nov 14 '05 #6

 P: n/a Eric Sosman wrote: If you're sure this is the algorithm you want to use, go ahead and implement it with an explicit stack of your own: a local array of start/end pairs plus an index indicating where the stack top is. [CUT] Eric, your post was very useful and teached my this new (new for me) use of a stack. Thank you very much!! Regards, Marco Nov 14 '05 #7

 P: n/a BQ wrote: CBFalconer wrote: You might start by making it easy for people to help you. 8 char indents are excessive, // comments don't survive line wrapping well, and any linelength over about 72 is likely to cause a problem on newsgroups. Do not use tabs, use spaces. Include dummy functions for the undefined things, so that people can compile it immediately. As it is the SearchSlaves operation seems singularly useless, since it returns nothing. Thanks CBFalconer, I'll keep it in mind when I'll write a post next time. Well, I thought you would post back with a cleaned up version. The first and obvious thing is to remove the tail recursion. That can automatically (with a choice of which half to recurse to) cut the maximum recursion depth to log2(n) with practically zero effort. After that there are straight forward mechanical methods for replacing recursion with a local stack. -- "I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare Nov 14 '05 #8

 P: n/a BQ wrote: Due to a lack of resources, I have to translate the following recursive function in its iterative form. It's a kind of dichotomic search. void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { char ret; //ping over a range of addresses //(all slaves with uid in the range // from start_uid to end_uid will reply) ret = PingSlave(start_uid,end_uid); if (start_uid == end_uid) //single item { if (ret == VALID_PING_REPLY) AddUidToSlaveList(start_uid); return; } if (ret == VALID_PING_REPLY) { // left subtree SearchSlaves(start_uid, ((start_uid + end_uid + 1) >> 1) - 1); // right subtree SearchSlaves(((start_uid + end_uid + 1) >> 1), end_uid); } } Any help will be greatly appreciated! I don't think that I can help you with your immediate problem but you should keep in mind that many C compilers will optimize [tail-]recursion for you. For example: cat factorial.c unsigned int factorial1(unsigned int n, unsigned int accumulator) { if (n == 0) return accumulator; else return factorial1(n - 1, n*accumulator); } unsigned int factorial(unsigned int n) { return factorial1(n, 1); } gcc -Wall -std=c99 -pedantic -O2 -S factorial.c cat factorial.s .file "factorial.c" .text .p2align 4,,15 .globl factorial1 .type factorial1, @function factorial1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl 12(%ebp), %eax jmp .L4 .p2align 4,,7 .L7: imull %edx, %eax decl %edx .L4: testl %edx, %edx jne .L7 popl %ebp ret .size factorial1, .-factorial1 .p2align 4,,15 .globl factorial .type factorial, @function factorial: pushl %ebp movl \$1, %eax movl %esp, %ebp subl \$8, %esp movl %eax, 4(%esp) movl 8(%ebp), %eax movl %eax, (%esp) call factorial1 leave ret .size factorial, .-factorial .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.4.1" Nov 14 '05 #9

 P: n/a CBFalconer wrote: Well, I thought you would post back with a cleaned up version. Sorry, I didn't do that because Eric had already answered my question. Anyway, here is the cleaned up version: void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) { if (start_uid == end_uid) { AddUidToSlaveList(start_uid); return; } SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1); SearchSlaves((start_uid+end_uid+1)/2, end_uid); } } The first and obvious thing is to remove the tail recursion. [CUT] After that there are straight forward mechanical methods for replacing recursion with a local stack. I agree with you and I think this will be the solution I'll chose, and I'll use Eric's function. Thank you all very much. Regards, Marco Nov 14 '05 #10

 P: n/a "E. Robert Tisdale" wrote: BQ wrote: Due to a lack of resources, I have to translate the following recursive function in its iterative form. It's a kind of dichotomic search. .... snip ... > gcc -Wall -std=c99 -pedantic -O2 -S factorial.c > cat factorial.s .file "factorial.c" .text .p2align 4,,15 .globl factorial1 .type factorial1, @function factorial1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl 12(%ebp), %eax It seems as if it is once again time to warn the various newbies out there that ANYTHING Trollsdale alias Tisdale posts is almost certainly off-topic, non-responsive, wrong, and designed purely to troll the newsgroup. The above is typical. -- "I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare Nov 14 '05 #11

 P: n/a BQ wrote: CBFalconer wrote: Well, I thought you would post back with a cleaned up version. Sorry, I didn't do that because Eric had already answered my question. Anyway, here is the cleaned up version: void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) { if (start_uid == end_uid) { AddUidToSlaveList(start_uid); return; } SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1); SearchSlaves((start_uid+end_uid+1)/2, end_uid); } } Which immediately becomes: void SearchSlaves(unsigned long start_uid, unsigned long end_uid) { while (PingSlave(start_uid, end_uid) == VALID_PING_REPLY) { if (start_uid == end_uid) { AddUidToSlaveList(start_uid); return; } SearchSlaves(start_uid, (start_uid + end_uid + 1) / 2) - 1); start_uid = (start_uid + end_uid + 1) / 2; } } Now if we have some knowledge of possible recursion level, it is easy to build a local stack with an array and an index, and eliminate the internal recursion. All it has to save is end_uid values and know when it is empty. You can write it in terms of push and pop, together with "if (stackempty) ...". Afterwards the push/pop/empty will become something like "stack[tos++] = value" and "value = stack[--tos]" and "if (tos) ...". Don't forget to initialize tos. -- "I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare Nov 14 '05 #12

 P: n/a CBFalconer wrote: [Concerning what amounts to a binary search written recursively] Well, I thought you would post back with a cleaned up version. The first and obvious thing is to remove the tail recursion. That can automatically (with a choice of which half to recurse to) cut the maximum recursion depth to log2(n) with practically zero effort. The code as shown already has a recursion depth of lg(n). How does eliminating one of the two recursive calls while leaving the other intact change that? Maybe it goes from lg(n) to lg(n)-1, but I don't see where any significant improvement arises. -- Eric Sosman es*****@acm-dot-org.invalid Nov 14 '05 #13

 P: n/a Eric Sosman wrote: CBFalconer wrote: [Concerning what amounts to a binary search written recursively] Well, I thought you would post back with a cleaned up version. The first and obvious thing is to remove the tail recursion. That can automatically (with a choice of which half to recurse to) cut the maximum recursion depth to log2(n) with practically zero effort. The code as shown already has a recursion depth of lg(n). How does eliminating one of the two recursive calls while leaving the other intact change that? Maybe it goes from lg(n) to lg(n)-1, but I don't see where any significant improvement arises. I was speaking in general. You are correct, in that his partitions are equi-sized. If they were not the improvement would apply. I had not bothered to read his code, because things were so ugly. Come to think of it, if the partitions are made with a size ratio of 1:2, and the 2 sized portion is handled with tail recursion, the overall depth will be reduced from log2(n) to log3(n). However the speed will be reduced. For some particular costs of comparison, calling, etc. there is probably an optimum ratio. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #14

 P: n/a CBFalconer wrote: BQ wrote: void SearchSlaves(unsigned long start_uid, unsigned long end_uid) if (start_uid == end_uid) //single item { if (ret == VALID_PING_REPLY) AddUidToSlaveList(start_uid); return; } As it is the SearchSlaves operation seems singularly useless, since it returns nothing. It doesn't need to; it adds found slaves to a list. Whether it's a good idea to have a (presumably single) global list for this is a different matter. Richard Nov 14 '05 #15

### This discussion thread is closed

Replies have been disabled for this discussion.