Help with an algorithm in C
Author 
Message 
Douglas A. Gwy #31 / 61

Help with an algorithm in C
Quote:
> on Recursion. My examples were:
I'm a big fan of Ackermann's function as an example of recursion. 

Mon, 10 Mar 2003 03:00:00 GMT 


Brian Evan Blan #32 / 61

Help with an algorithm in C
Quote:
> >Well, if someone were to ask me, I might well use factorials > I've watched this thread for a while and sat on my hands, however, this > goes a bit too far. > If you wish to teach recursion, then you should never in the process > teach people to make elementary mistakes. It has already been pointed > out that factorials increase so rapidly that without multiple precision > even the smallest of factorials produce integer overflows. If > factorials are to serve as the example, then at least use the GNU > multiple precision library, gpm.
Shocking! Someone who knows as much C as Peter Seebach should be teaching people to make advanced mistakes. On second thought, ... without recourse to a multiple precision library, the program below uses recursion to calculate all factorials less than pow(10,1344). I don't think that there is any integer overflow. The program scales easily to handle much larger numbers but since there are only about 136*pow(2,256) protons in the universe I thought that pow(10,1344) would be sufficiently large for the purposes of a newsgroup. Ordinarily I selfcensor any contemplated response to an article crossposted to a distinguished forum, but perhaps the moderator will allow this one to sneak through. #include <stdio.h> #include <stdlib.h> #include <math.h> #define tooLarge 577 #define tableSize 105 int powerOfPrimeInFactorial(int, int, int); void usage(void){ printf("nFactr: Recursively computes and factors n!\n" "usage : nFact n\n " "where n is a nonnegative integer less than %d\n",tooLarge); exit(EXIT_FAILURE); Quote: }
int main(int argc, char*argv[]){ int ithprime[tableSize] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571 Quote: };
unsigned n; int i=0; if(2 != argc  (n =(unsigned)atoi(argv[1])) >= 577) usage(); if(n <= 1) printf("%u! = 1\n",n); else{ printf("\n%u! = ",n); while(i < tableSize && ithprime[i] <= (int) n){ printf("(%d^%u)*",ithprime[i],powerOfPrimeInFactorial(ithprime[i],n,1)); i++; } printf("\b.\n"); } return EXIT_SUCCESS; Quote: }
int powerOfPrimeInFactorial(int p, int n, int k){ if(pow(p,k) > n) return 0; return (int)floor(n/pow(p,k)) + powerOfPrimeInFactorial(p, n, k+1); Quote: }
(To reach me, replace my middle name with my first.)  Brian Blank You cannot program Department of Mathematics a crooked machine Washington University in St. Louis to go straight. St. Louis, MO 63130 Edsger Dijkstra 

Mon, 10 Mar 2003 03:00:00 GMT 


Peter Seeba #33 / 61

Help with an algorithm in C
Quote: >Shocking! Someone who knows as much C as Peter Seebach should be >teaching people to make advanced mistakes.
Well, I did go out of my way to include the strtok one, which has bitten many, many, people... Quote: >On second thought, ... >without recourse to a multiple precision library, the program below >uses recursion to calculate all factorials less than pow(10,1344).
Uhm. No offense is meant, but I think this pretty much kills any concern I may have had that *my* example was opaque. :) s 
C/Unix wizard, Procommerce radical, Spam fighter. Boycott Spamazon! Consulting & Computers: http://www.plethora.net/ 

Mon, 10 Mar 2003 03:00:00 GMT 


Ariel Scolnico #34 / 61

Help with an algorithm in C
Quote:
> > Well, if someone were to ask me, I might well use factorials (or perhaps > > the even more abusive Fibonacci series) as an example, but I suspect I could > > be persuaded to then explain how to convert these to be nonrecursive, and > > explain why they're bad examples. > I really wouldn't use the Fibonacci series as an example, because the > straightforward code takes O (F (n)) units in time instead of O (n), so it > only gives the wrong impression that recursion is terribly inefficient.
I really would care to use the Fibonacci series as an example. While the "straightforward" code takes O(F_n) units of time (where all arithmetic is performed in O(1)) to compute F_n, and the trivial loop code takes time O(n) to compute it, by using the O(log n) n'th power algorithm you can compute F_n in time O(log n). And the underlying "log power" algorithm gets used all over the place; even the carry lookahead adder is a relative. That algorithm for Fibonacci numbers may be expressed recursively fairly well. A commented version would take the trouble to explain the algorithm I'm blathering about :) Something like this is nice: struct sym22 { /* matrix is [[a b] [b c]] */ long a,b,c; }; struct sym22 fib_helper(int n) { struct sym22 ret, val; if (n == 1) { ret.a = 1; ret.b = 1; ret.c = 0; } else if (n % 2 == 0) { val = fib_helper(n/2); ret.a = val.a*val.a + val.b*val.b; ret.b = val.b * (val.a+val.c); ret.c = val.b*val.b + val.c*val.c; } else { val = fib_helper(n1); ret.a = val.a + val.b; ret.b = val.a; ret.c = val.b; } return ret; } long fib(int n) { struct sym22 val; if (n == 0) return 0; else if (n == 1) return 1; else { val = fib_helper(n1); return val.a; } } (Yes, I know this can be programmed iteratively). Quote: > On the other hand, "recursion" is just a very special case of a function > call, so I am not sure if there is indeed any need to learn something > special about this case.
It's a programming technique. It has its uses. It also has its abuses. Syntactically, it's just there. You still want to learn (and teach) it, though. 
Compugen Ltd. Tel: +97225713025 (Jerusalem) \ We recycle all our Hz 72 Pinhas Rosen St. Tel: +97237658514 (Main office)` TelAviv 69512, ISRAEL Fax: +97237658555 http://3w.compugen.co.il/~ariels 

Mon, 10 Mar 2003 03:00:00 GMT 


Francis Glassboro #35 / 61

Help with an algorithm in C
Quote: > If the argument is that it's a simple example because the student >can't understand anything more complicated yet, then you're doing a >disservice to the students by trying to teach them something they can't >use yet. In this case, it would be far better to wait a while until >they have enough skill that they can use recursion effectively. The >canonical, NONtrivial example of recursion is traversing a tree. I >think it would be far better to hold off on teaching recursion until you >can demonstrate it with a solid, USEFUL example such as this.
The question was 'what is recursion?' Had it been 'what is recursion good for?' or ''what are the problems with recursion?' I would give very different answers. I do not wish to spend time explaining problems, so that I can respond to the simple question asked. Seriously, that question can be asked by people who know next to nothing about programming and probably wish they knew even less. Francis Glassborow Association of C & C++ Users 64 Southfield Rd Oxford OX4 1PA +44(0)1865 246490 All opinions are mine and do not represent those of any organisation 

Mon, 10 Mar 2003 03:00:00 GMT 


cbfalco.. #36 / 61

Help with an algorithm in C
Quote:
> >If you wish to teach recursion, then you should never in the > >process teach people to make elementary mistakes. It has already > >been pointed out that factorials increase so rapidly that without > >multiple precision even the smallest of factorials produce integer > >overflows. > Which is an excellent reason for using them, it will help students > to become quickly aware of the dangers of recursion. I used to have > a very nice flood fill recursive algorithm that showed another of > the dangers. The algorithm was expressive and its working was > almost transparent. Then students would realise that it stacked the > coordinates of every point in the closed area before it used any > of them, the result blew most stacks. > Getting failure in a controlled learning environment can be very > educational without causing serious danger. > Francis Glassborow Association of C & C++ Users
Even if aware, some language implementations can bite. Some years ago I designed something or other recursive in Turbo Pascal. The parameters and locals were closely controlled, either small or passed by reference. It blew up with stack overflows!! It turned out that the implementation assigned two hidden large internal temporaries for an elementary string operation, even though the actual strings were much shorter. The cure was a helper function so that this only happened once, rather than within the recursion. Without a de{*filter*}, and looking at the machine code generated and register values, it would have been almost impossible to find the cause. There was no documentation of the local assignment action. I suspect that such is not very likely in most C applications, but C++ would be a different story with various hidden conversions, etc. Many people today are totally unaware of the costs, with gigabyte virtual memory expanses and automatic stack extension etc. 
http://www.***.com/ 

Mon, 10 Mar 2003 03:00:00 GMT 


Jerry Coffi #37 / 61

Help with an algorithm in C
[ good and bad examples of recursion ] Quote: > How about a binary search through an array?
A mediocre example, IMO. Given typical array sizes, it's at least not generally particularly terrible, but it's still not particularly good. The recursive version at least isn't terrible as is the case with something like a recursive Fibonacci function, but recursion doesn't make the code any shorter, simpler or easier to understand, while it usually does make it take more memory and time to run. By contrast, searching a binary tree recursively is a LOT simpler than doing so iteratively. It might be a tiny bit slower and use a tiny bit more memory, but most people will quickly agree that the simplicity and transparency of the code compensates at least the vast majority of the time. Quote: > You see, Peter follows up > his explanation of why recursive Fibonacci is lame with a much more > practical demonstration using a binary search.
I'd replace "much more practical" with "somewhat less impractical." Quote: > His hands were tied to a > certain extent, by the fact that sorting, expression evaluation, and > trees were all covered already in separate chapters of this hypothetical > book that he keeps going on about.
...the one that's apparently NOT hypothetical at all in reality? IMO, recursion is a method of implementing algorithms, and trying to cover it separately from the algorithms that really benefit from using it was a poor decision to start with. I realize that when writing a book, especially for beginners, figuring out how to organize things so the earlier parts don't need later parts can be _extremely_ difficult, but my immediate take is that in this case the best choice is probably to try to rethink the ordering a bit. Quote: > > It _might_ be educational to show a non > > recursive version of at least one to show WHY recursion can be so > > useful. > Well, Peter sort of does this the other way around, by showing how > recursion can be eliminated from the factorial and Fibonacci examples.
Understanding recursion usually takes some time and effort on the part of the student. The average student's simply not going to bother with that until or unless you show him/her some REAL advantage to doing so.  Later, Jerry. The Universe is a figment of its own imagination. 

Thu, 13 Mar 2003 10:45:45 GMT 


Richard Heathfiel #38 / 61

Help with an algorithm in C
Quote:
> [ good and bad examples of recursion ] > > How about a binary search through an array? > A mediocre example, IMO. Given typical array sizes, it's at least > not generally particularly terrible, but it's still not particularly > good. The recursive version at least isn't terrible as is the case > with something like a recursive Fibonacci function, but recursion > doesn't make the code any shorter, simpler or easier to understand, > while it usually does make it take more memory and time to run.
I hate to disagree with you, but I disagree with you. I've found that my "students" (none right now, thank heaven, but I occasionally get graduate trainees dumped on me) catch on to recursion very quickly when I use binary search as the example. They aren't quite ready to make the leap (back? ;) ) to the trees, but they do implicitly understand the recursive concept of chucking half of an array away, once it's explained to them. Quote: > By contrast, searching a binary tree recursively is a LOT simpler > than doing so iteratively. It might be a tiny bit slower and use a > tiny bit more memory, but most people will quickly agree that the > simplicity and transparency of the code compensates at least the vast > majority of the time.
Right, and that's clearly the next example to use, but not until the student is ready for trees. Quote: > > You see, Peter follows up > > his explanation of why recursive Fibonacci is lame with a much more > > practical demonstration using a binary search. > I'd replace "much more practical" with "somewhat less impractical."
Well, you have the right to your opinion, of course. :) Quote: > > His hands were tied to a > > certain extent, by the fact that sorting, expression evaluation, and > > trees were all covered already in separate chapters of this hypothetical > > book that he keeps going on about. > ...the one that's apparently NOT hypothetical at all in reality?
Yep, that's the one. :) Quote: > IMO, recursion is a method of implementing algorithms, and trying to > cover it separately from the algorithms that really benefit from > using it was a poor decision to start with.
Well, blame me, then, rather than Peter. Quote: > I realize that when > writing a book, especially for beginners,
The book isn't for beginners. But its contents were determined /by/ a beginner. Me. This probably explains a lot! But I don't think it's turned out too badly. At least, I haven't forged the reviews of it that I've seen... But then I haven't yet found an ACCU review of it. :% Quote: > figuring out how to > organize things so the earlier parts don't need later parts can be > _extremely_ difficult, but my immediate take is that in this case the > best choice is probably to try to rethink the ordering a bit.
I'm reasonably happy with the ordering 'as is'; I wanted the recursion to precede the discussions of data structures such as trees, and algorithms such as parsing, to give the nonrecursionaware reader a fighting chance of swimming rather than sinking in those areas. Quote: > > > It _might_ be educational to show a non > > > recursive version of at least one to show WHY recursion can be so > > > useful. > > Well, Peter sort of does this the other way around, by showing how > > recursion can be eliminated from the factorial and Fibonacci examples. > Understanding recursion usually takes some time and effort on the > part of the student. The average student's simply not going to > bother with that until or unless you show him/her some REAL advantage > to doing so.
Whatever happened to students who did as they're told? :)  Richard Heathfield "Usenet is a strange place."  Dennis M Ritchie, 29 July 1999. C FAQ: http://www.eskimo.com/~scs/Cfaq/top.html 65 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (32 to go) 

Wed, 19 Mar 2003 03:00:00 GMT 


Ben Pfaf #39 / 61

Help with an algorithm in C
Quote:
> By contrast, searching a binary tree recursively is a LOT simpler > than doing so iteratively.
What? You're saying that if (node == NULL) return NULL; else if (a > node>data) return search (a, node>right); else if (a < node>data) return search (a, node>left); else return node; is a LOT simpler than for (; node != NULL; ) if (a > node>data) node = node>right; else if (a < node>data) node = node>left; else break; return node; I don't understand, please explain. What's more, you probably need two functions for the recursive solution, one with the code above and another to extract the root from the tree structure, whereas only one is needed for the iterative solution. [enormous snippage]  "I ran it on my DeathStation 9000 and demons flew out of my nose." Kaz 

Wed, 19 Mar 2003 03:00:00 GMT 


John Pott #40 / 61

Help with an algorithm in C
Quote:
> [ good and bad examples of recursion ] > > How about a binary search through an array?
What does a search produce? Let's take the example of search returning a pointer the the left most element greater than or equal to the target. This is a lower bound which indicates where the target should be. In the case where the target is greater than all elements, the return is one past the end. Call with (table, table + N, target). Quote: > A mediocre example, IMO. Given typical array sizes, it's at least > not generally particularly terrible, but it's still not particularly > good. The recursive version at least isn't terrible as is the case > with something like a recursive Fibonacci function, but recursion > doesn't make the code any shorter, simpler or easier to understand, > while it usually does make it take more memory and time to run.
The unnatural use of ?: in the first function is to balance it with the other three where it was natural (for me). typedef int* Pos; Pos lowerAI (Pos lo, Pos hi, int target) { while (lo != hi) { Pos mid = lo + (hi  lo) / 2; int delta = *mid < target; *(delta ? &lo : &hi) = mid + delta; } return lo; } Pos lowerAR (Pos lo, Pos hi, int target) { Pos mid = lo + (hi  lo) / 2; return lo == hi ? lo : *mid < target ? lowerAR(mid + 1, hi, target) : lowerAR(lo, mid, target); } I think this supports your claim. Quote: > By contrast, searching a binary tree recursively is a LOT simpler > than doing so iteratively. It might be a tiny bit slower and use a > tiny bit more memory, but most people will quickly agree that the > simplicity and transparency of the code compensates at least the vast > majority of the time.
I guess that I am not most people. typedef struct Node* Tree; struct Node { Tree left, right; int data; }; Tree lowerTI (Tree root, int target) { Tree result = 0; while (root) root = root>data < target ? root>right : (result = root)>left; return result; } Tree lowerTRhelper (Tree root, int target, Tree best) { return root ? root>data < target ? lowerTRhelper(root>right, target, best) : lowerTRhelper(root>left, target, root) : best; } Tree lowerTR (Tree root, int target) { return lowerTRhelper(root, target, 0); } I do not see the recursive version as superior in any way. Maybe you really intended to use traversal as the example. Quote: > IMO, recursion is a method of implementing algorithms, and trying to > cover it separately from the algorithms that really benefit from > using it was a poor decision to start with.
Agreed, almost. Quote: > Understanding recursion usually takes some time and effort on the > part of the student. The average student's simply not going to > bother with that until or unless you show him/her some REAL advantage > to doing so.
Agreed. Given a recursive data structure like a tree and an algorithm like traversal which depends upon the recursive nature of the structure, it makes sense to think recursively. Recursion is a method of solving problems. Recursive programs are the natural result of solving problems recursively. Demonstrating the workings of a recursive program will not lead to recursive thinking. The Fibonacci recursive version is a natural implementation of a function which is defined recursively. Looking at the workings of the algorithm shows that it is a poor implementation. Producing the iterative version involves examination of the sequence not simple code manipulation like tail recursion removal. Further examination leads to faster, more complex versions. If the goal is problem solving, factorial is a simple example. If the goal is coding, factorial is a horrid example. John 

Wed, 19 Mar 2003 03:00:00 GMT 


Nils Goesch #41 / 61

Help with an algorithm in C
Quote:
> > Understanding recursion usually takes some time and effort on the > > part of the student. The average student's simply not going to > > bother with that until or unless you show him/her some REAL advantage > > to doing so. > Agreed. Given a recursive data structure like a tree and an algorithm > like traversal which depends upon the recursive nature of the structure, > it makes sense to think recursively. Recursion is a method of solving > problems. Recursive programs are the natural result of solving > problems recursively. Demonstrating the workings of a recursive > program will not lead to recursive thinking. > The Fibonacci recursive version is a natural implementation of a > function which is defined recursively. Looking at the workings > of the algorithm shows that it is a poor implementation. Producing > the iterative version involves examination of the sequence not > simple code manipulation like tail recursion removal. Further > examination leads to faster, more complex versions. > If the goal is problem solving, factorial is a simple example. If > the goal is coding, factorial is a horrid example.
Once in a bar I explained recursion to a philosophy major without any mathematical or programming background. I used the towers of Hanoi as an example and after a few minutes he completely understood. At first, he tried to imagine how and when the function calls itself during the process and failed, of course. Then I told him not to try to imagine how it calls itself, but rather make an inductive proof that the function works as intended (I explained inductive proofs on the fly :). I still remember the moment when I understood recursion myself, and that was exactly when I had the idea to make an inductive proof that it works, rather than think about _how_ it works. It worked for him, too. And this Hanoi tower example is easy to understand (in binary search it is somewhat hard to ensure that you get the bounds right) and also a good example where recursion is the _right_ approach to solve the problem. Unfortunately, it seems that CS teachers are used to give the Hanoi tower example as a homework exercise rather than using it for explaining recursion.  Nils Goesche Ask not for whom the <CONTROLG> tolls. 

Sat, 22 Mar 2003 13:22:20 GMT 


Jerry Coffi #42 / 61

Help with an algorithm in C
says... [ ... ] Quote: > I do not see the recursive version as superior in any way. Maybe you > really intended to use traversal as the example.
Yes, I did. Quote: > The Fibonacci recursive version is a natural implementation of a > function which is defined recursively. Looking at the workings > of the algorithm shows that it is a poor implementation. Producing > the iterative version involves examination of the sequence not > simple code manipulation like tail recursion removal. Further > examination leads to faster, more complex versions. > If the goal is problem solving, factorial is a simple example. If > the goal is coding, factorial is a horrid example.
I guess I'll buy that general idea. The problem is that (at least IMO) defining factorial recursively is more or less a problem by itself. It appears to me that at least for most people, a recursive definition of factorial is something of a problem  when I've told people a recursive definition, I usually end up pointing out that it's just a different way of stating the iterative version. In every case I can recall, their immediate reaction is something like "well why didn't you just say that to start with?" I guess given the constraints that Richard has since stated: no sorting, no searching, no parsing, etc., that generating the Fibonacci series recursively makes about as much sense as most of the other obvious examples. OTOH, even within that set of constraints, I'd agree with the other suggestion made in this thread that Euclid's algorithm for finding GCDs is probably a better choice: a recursive version is fairly straightforward without losing enough efficiency for most people to care much about.  Later, Jerry. The universe is a figment of its own imagination. 

Sat, 22 Mar 2003 03:00:00 GMT 


Jerry Coffi #43 / 61

Help with an algorithm in C
says... Quote:
> > By contrast, searching a binary tree recursively is a LOT simpler > > than doing so iteratively. > What? You're saying that
[ recursive code ] Quote: > is a LOT simpler than
[ iterative code ] Quote: > I don't understand, please explain.
The explanation's really simple: I screwed up. I intended to say traversale, not searching. E.g. an inorder traversal expressed recursively is something like: void traverse(node *tree) { if (NULL == tree) return; traverse(tree>left); apply_func(tree>data); traverse(tree>right); Quote: }
In reality, you typically end up passing a pointer to a function as well, but the basic idea's pretty simple and straightforward. Pre and post order traversal are equally simple. Importantly, all three are simple enough that it's trivial for nearly any student to follow the differences and keep track of what's going on. OTOH, if you try to implement this with iterative code, you'll quickly find that bookkeeping dominates the picture, and the tree traversal itself almost gets lost in the muddle.  Later, Jerry. The universe is a figment of its own imagination. 

Sat, 22 Mar 2003 03:00:00 GMT 


Jerry Coffi #44 / 61

Help with an algorithm in C
[ ... ] Quote: > > IMO, recursion is a method of implementing algorithms, and trying to > > cover it separately from the algorithms that really benefit from > > using it was a poor decision to start with. > Well, blame me, then, rather than Peter.
I'm considerably less interested in allocating blame than in helping produce a better book. There may have been reasons it would have been impractical to do so, but from this viewpoint, I think it might have been better to have this discussion before the book was written rather than afterwards. Quote: > > Understanding recursion usually takes some time and effort on the > > part of the student. The average student's simply not going to > > bother with that until or unless you show him/her some REAL advantage > > to doing so. > Whatever happened to students who did as they're told? :)
Long before they got to the point of learning about programming, they (hopefully) learned to think for themselves to at least some degree. Then again, I think that even if they sincerely study and TRY to follow along, if they can't help thinking that something is silly, they're less likely to retain it well than if it makes sense.  Later, Jerry. The universe is a figment of its own imagination. 

Sat, 22 Mar 2003 03:00:00 GMT 


