Re: Recursive Functions

From: Julian V. Noble (jvn_at_nowhere.virginia.edu)
Date: 10/30/03 

Date: Wed, 29 Oct 2003 22:51:10 -0500

Richard Heathfield wrote:
>
> Glen Herrmannsfeldt wrote:
>
> >
> > "Marcus Lessard" <spam08@spam.com> wrote in message
> > news:bnlrqm$qg2$1@pyrite.mv.net...
> >> Maybe it's just me but doesn't the contrived nature of the function
> >> scream
> >> out "Homework Assignment?" Maybe I'm missing something but I just can't
> > see
> >> why you'd ever want to compute this value..
> >
> > Computing integer powers of numbers is fairly common in scientific
> > programming, and is one of the relatively few things missing from C used
> > in scientific programming.
> >
> > However, requiring it as a recursive function does scream of homework. A
> > simple for loop should be easier and faster.
>
> Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
> result occupies over 6500 decimal digits, I won't display it here!)
>
> The recursive calculation took 0.22 seconds, and the iterative version 1.06
> seconds - almost five times slower. Perhaps you could demonstrate an
> iterative version that can hold a candle to the recursive technique?
>
> --
> Richard Heathfield : binary@eton.powernet.co.uk
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R answers, C books, etc: http://users.powernet.co.uk/eton

To compare recursive and iterative versions you have to know what is
happening at the machine level. Some processors do recursion faster
because they can parallelize stack ops with arithmetic ops.

I found that the recursive version of the extended Euclid algorithm
for greatest common divisor runs 20-30% faster than the iterative
version given by Knuth, on Pentium-class machines.

I expect this would not be true on machines with enough registers that
all the intermediate results could be allocated to registers. 

-- 
Julian V. Noble
Professor Emeritus of Physics
jvn@lessspamformother.virginia.edu
    ^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/
   "Science knows only one commandment: contribute to science."
   -- Bertolt Brecht, "Galileo".

Relevant Pages

  • Re: Response to Karen and to Willem on recursive proofs
    ... > Could you give an example of a correctness proof involving recursion? ... // But since it can be seen by inspection of the loop termination condition ... // Recursion in programming is, of course, a subroutine calling itself. ...
    (comp.programming)
  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... There are no expressions in Fortran or Pascal??! ... expressions are programming language constructs that return a value. ... > languages don't have recursion. ...
    (sci.math.symbolic)
  • Re: Another way to do x^n
    ... think carefully about writing code readable by folks who aren't Forth ... But the Forth programming culture is one of egotistical cleverness, ... Very handy for things like parsers. ... But there are enormous application areas where recursion is of no advantage, and its employment just obfuscates the code. ...
    (comp.lang.forth)
  • Re: This one goes to 11
    ... programming language and have it immediately executed during debugging. ... and especially tail recursion. ... Common Lisp cover all the important cases in a convenient, ...
    (comp.lang.lisp)
  • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
    ... > recursion to define an ordered set, that does not imply (as you imply ... programming in something like Java. ... >>> abandon Java in favour of a toy language that is limited to them and no ...
    (comp.programming)