Help with an algorithm in C 
Author Message
 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  
 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 self-censor any contemplated response to an article
cross-posted 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  
 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, Pro-commerce radical, Spam fighter.  Boycott Spamazon!
Consulting & Computers: http://www.plethora.net/
--



Mon, 10 Mar 2003 03:00:00 GMT  
 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 non-recursive, 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(n-1);
        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(n-1);
        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: +972-2-5713025 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658514 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels
--



Mon, 10 Mar 2003 03:00:00 GMT  
 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, NON-trivial 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  
 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
> co-ordinates 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  
 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 re-think 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  
 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 re-think 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 non-recursion-aware 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/C-faq/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  
 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  
 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  
 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 <CONTROL-G> tolls.
--



Sat, 22 Mar 2003 13:22:20 GMT  
 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  
 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 in-order 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 book-keeping 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  
 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  
 
 [ 61 post ]  Go to page: [1] [2] [3] [4] [5]

 Relevant Pages 
 

 
Powered by phpBB® Forum Software