Home > Archive > Unix Programming > March 2008 > Books on recursive programming?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Books on recursive programming?
|
|
| saneman 2008-03-09, 9:16 am |
| Are there any good books covering recursive programming for beginners?
I have read that recursive programming should be slow and waste a lot of
space. Is that why most programs avoid this style (I almost never come
across programs using recursions).
Or are there cases where a problem is solved much more efficient with
recursions?
| |
| Ben Bacarisse 2008-03-09, 9:16 am |
| saneman <asdfsdf@asd.com> writes:
> Are there any good books covering recursive programming for
> beginners?
Odd post for comp.unix.progrmmer. You'll get more answers on
comp.programming.
Look for books about functional programming. All functional
programming languages make heavy use of recursion. There are so many
books about this topic that I can't make a recommendation without
knowing much more about the sort of book you might take to.
> Or are there cases where a problem is solved much more efficient with
> recursions?
Recursion is such a natural choice when handling data structures that
are inherently recursive (like binary trees) that it is often not worth
using any other method.
--
Ben.
| |
| Mark Hobley 2008-03-09, 9:16 am |
| saneman <asdfsdf@asd.com> wrote:
> Are there any good books covering recursive programming for beginners?
I ran "recursive programming" through Amazon book search, and a load of
books came up, but I haven't looked at any of these, so I have no
specific recommendations. (Some books provide an index page and possibly a
sample chapter, to give you the idea of the content and style of the
book.)
There are also a variety of papers scattered about the internet that you
could try looking at.
> I have read that recursive programming should be slow and waste a lot of
> space. Is that why most programs avoid this style (I almost never come
> across programs using recursions).
I think it is just that general programming problems can usually be
solved in other ways, by using modular programming techniques.
Some people may find ecursive programs may be difficult to debug, and
may possibly require specialized recursive debugging tools.
> are there cases where a problem is solved much more efficient with
> recursions?
The cases I have seen for recursive programming are for solving
mathematical or evolutionary problems, and for re-entrant interrupts (ie
an interrupt that gets interrupted by itself or indirectly via circular
events.)
Do you have a specific application in mind?
Mark.
--
Mark Hobley,
393 Quinton Road West,
Quinton, BIRMINGHAM.
B32 1QE.
| |
| Rainer Weikusat 2008-03-09, 9:16 am |
| saneman <asdfsdf@asd.com> writes:
> I have read that recursive programming should be slow and waste a lot
> of space.
That's just a special case of the more general belief that code must
not be structured because 'function call overhead' would be to
expensive ('recursion' basically means to use nested calls of a
function [or some set of functions] with changing arguments instead of
loops).
[...]
> Or are there cases where a problem is solved much more efficient with
> recursions?
This depends on what sort of 'efficiency' is being considered. A
practical example: A program I am working on is supposed to act as
SNMP gateway to some set of appliances, eg to receive unecrypted and
'insecure' SNMP v1 and v2c requests coming from a management station
sitting on a 'trusted' network and use existing software for secure,
message based communication to convey the 'meaning' of these requests
to appliance spread 'all around the internet'. One of the things this
program needs to do is to analyze the syntactic structure (ASN.1
subset) of SNMP requests and build a more easily accessible data
structure representing that, which other parts of the program then use
to perform 'certain operations' on it. A 'SNMP type' is either one
from a set of primitive types or a sequence of other SNMP types. The
basic routine build a list of descriptor structures for a 'sequence'
(here meaning 'linear concatentation of'[*]) SNMP type
descriptions iteratively. Depending on the 'current' type, it either
calls a subroutine to further analyze a 'primitive type' or a
subroutine to further analyze a sequence type. The sequence type
analysis routine ultimatively calls the same basic routine to
analyse the 'sequence of SNMP-types' contained in the SNMP sequence
type. Basically, this means that the compiler will handle the
management of the data structures necessary to analyze an arbitrarily
deeply nested sequence[*] of SNMP types on its own, which reduces the
amount of code needing to be written for that.
The 'canonical' way to solve such a problem would, of course, just be
'use the existing BSD-licensed SNMP code, which workd somehow' (and
hire one of its authors as consultant if 'somehow' is either to
incomprehensible to be used or not really usable for a particular task
at all ... honi soit qui mal y pense ...).
| |
| Aaron Hsu 2008-03-09, 7:27 pm |
| saneman <asdfsdf@asd.com> writes:
> Are there any good books covering recursive programming for beginners?
If you want, you can try the idiomatic book, ``Structure and
Interpretation of Computer Programs,'' which is a programming book
designed to introduce all the basic concepts of computer science. It
uses Lisp (Scheme) as its language, and Scheme is basically ALL recursion.
> I have read that recursive programming should be slow and waste a lot
> of space. Is that why most programs avoid this style (I almost never
> come across programs using recursions).
Absolutely not true. On limited processors and such, stacks can be of
limited size and therefore general recursion may not be desirable
there. However, for modern machines in most cases of UNIX, this is not
much of a problem. There are many programming tasks that are solved
naturally with Recursion.
Another thing to note is that there is such a thing as Tail
Recursion. Good C compilers and all copmliant Scheme implementations
treat these tail recursion in such a way that the total memory consumed
on successive iterations (meaning the total memory consumed by a tail
recursive function) is equal to one stack frame of the function call,
roughly speaking. In other words, it's as effecient as an iteration,
sometimes more so.
> Or are there cases where a problem is solved much more efficient with
> recursions?
There are plenty of problems that are more naturally solved with
recursion. Depending on the nature of your program, sometimes, there are
certain properties of a recursive algorithm that can make it faster than
an iterative one given unique circumstances, but in general, iteration
and recursion should not be significantly different in speed except when
dealing with large and deeply nested non-tail recursions on a bad
compiler and a slow or limited processor.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Rainer Weikusat 2008-03-10, 8:16 am |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> saneman <asdfsdf@asd.com> writes:
[...]
>
> Absolutely not true.
To the contrary, in absence of compiler tricks to eliminate a
recursion automatically, a recursive implementation of some algorithm
will always run slower and use more space than an iterative one, for
the simple reason that a lot more subroutine calls are needed, which
take time to do and memory to store the associated meta-data. This is
especially true on architecturally outdated and feebly capable
processors, like all x86-variants.
> On limited processors and such, stacks can be of
> limited size and therefore general recursion may not be desirable
> there.
'Stack' is always of 'a limited size' because every computer has only
a finite amount of memory. This has nothing to do with
'processors'. Depending on the environment, stack may well be very
limited, eg when code is part of a Linux-kernel configured to use 4K
per-thread stacks.
> However, for modern machines in most cases of UNIX, this is not
> much of a problem. There are many programming tasks that are solved
> naturally with Recursion.
Every algorithm using a loop with a finite number of iterations can be
expressed recursively. No computer algorithm can ever be 'natural',
because it is something completely artifical made by man (the same is
more generally true for 'everything mathematic', this being another
thing invented by man).
> Another thing to note is that there is such a thing as Tail
> Recursion. Good C compilers and all copmliant Scheme implementations
> treat these tail recursion in such a way that the total memory consumed
> on successive iterations (meaning the total memory consumed by a tail
> recursive function) is equal to one stack frame of the function call,
> roughly speaking. In other words, it's as effecient as an iteration,
> sometimes more so.
This is bollocks. Tail-recursive algorithms can be translated to
iterative algorithms very easily, and some compilers occasionally do
so automatically. This is a very important part of the job of an
so-called 'optimizing compiler': Detect parts of an implementation
which only exist because of some programmer delusion and replace them
with more sensible variants.
Because tail-recursive algorithms can easily be translated into
iterative algorithms, they are 'use of recursion for the sake of using
recursion' and should be avoided.
>
> There are plenty of problems that are more naturally solved with
> recursion.
Depending on the 'mental universe' someone programming a computer
lives in, it may be more easy for him to use either recursion or
iteration.
> Depending on the nature of your program, sometimes, there are
> certain properties of a recursive algorithm that can make it faster than
> an iterative one given unique circumstances, but in general, iteration
> and recursion should not be significantly different in speed
A not entirely unreasonable definition of 'insignificant difference'
would be 'a difference someone doesn't care about'. Which means
nothing except that someone doesn't care for the difference.
| |
| Aaron Hsu 2008-03-10, 7:49 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
> [...]
>
>
> To the contrary, in absence of compiler tricks to eliminate a
> recursion automatically, a recursive implementation of some algorithm
> will always run slower and use more space than an iterative one, for
> the simple reason that a lot more subroutine calls are needed, which
> take time to do and memory to store the associated meta-data.
However, saneman says, ``should be slow,'' and this simply isn't
true. The simple fact that an algorithm is recursive should not
inherently demand that the algorithm is also slow and excessively
wasteful, which is how I read the above. Yes, recursive algorithms can
have a higher overhead through function calls and stack usage, but this
isn't necessarily what should happen just because an algorithm is
recursive.
>
> 'Stack' is always of 'a limited size' because every computer has only
> a finite amount of memory. This has nothing to do with
> 'processors'. Depending on the environment, stack may well be very
> limited, eg when code is part of a Linux-kernel configured to use 4K
> per-thread stacks.
Agreed, I was using sloppy terminology here. My meaning was that for
many commonly used systems and user-level applications the amount of
stack space available to the system is large enough to that very deeply
non-tail recursive, non-optimized algorithms generally don't have too
much trouble, IME.
>
> Every algorithm using a loop with a finite number of iterations can be
> expressed recursively. No computer algorithm can ever be 'natural',
> because it is something completely artifical made by man (the same is
> more generally true for 'everything mathematic', this being another
> thing invented by man).
Using this definition, than yes, I agree. And, yes, iteration and
recursion can substitute each other, but that doesn't mean that one is
as simple or intuitive to implement as the other for a given problem.
>
> This is bollocks. Tail-recursive algorithms can be translated to
> iterative algorithms very easily, and some compilers occasionally do
> so automatically. This is a very important part of the job of an
> so-called 'optimizing compiler': Detect parts of an implementation
> which only exist because of some programmer delusion and replace them
> with more sensible variants.
>
> Because tail-recursive algorithms can easily be translated into
> iterative algorithms, they are 'use of recursion for the sake of using
> recursion' and should be avoided.
I disagree. For some compilers, the compiler is capable of generating
more efficient code from a recursively defined algorithm that it can
optimize, which utilizes little in the way of explicit assignments, than
can the equivalently easy to write iterative algorithm. It may be
possible to make the two equal in total efficiency at the end, but some
problems are easier to understand in the source code when reading and
writing them if they are written recursively.
Specifically, in my experience, certain compilers do a better job of
optimizing code which is written in a recursive, functional style, than
it does optimizing the equivalent code writen in an imperative,
assignment based iterative style. Thus, if the OP happens to be using
such a compiler, then it may be better to use a recursive style as
opposed to the iterative one.
Recursion, imo, should not be avoided simply because you can solve a
problem iteratively, but the method to use should be chosen on the basis
of what is more readable and maintainable and/or easier to write.
>
> Depending on the 'mental universe' someone programming a computer
> lives in, it may be more easy for him to use either recursion or
> iteration.
True, and since this is the case, I think that silly rules like, ``avoid
recursion as much as possible,'' should be thrown away, since usually
the choice of recursion vs. iteration isn't such a big problem, and it's
more important for the programmer to write ``intuitive'' code, for some
rough definition of intuitive.
>
> A not entirely unreasonable definition of 'insignificant difference'
> would be 'a difference someone doesn't care about'. Which means
> nothing except that someone doesn't care for the difference.
Yes. The point I was trying to make is that the gospel preaching of
``avoid recursion because it's too expensive'' is wrong, and shouldn't
be accepted as a coding guideline. Rather, code should be evaluated on
the actual results, and the results judged for what they are, without
the restrictive and relatively useless bias against recursion.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Aaron Hsu 2008-03-10, 7:49 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
> [...]
>
>
> To the contrary, in absence of compiler tricks to eliminate a
> recursion automatically, a recursive implementation of some algorithm
> will always run slower and use more space than an iterative one, for
> the simple reason that a lot more subroutine calls are needed, which
> take time to do and memory to store the associated meta-data.
However, saneman says, ``should be slow,'' and this simply isn't
true. The simple fact that an algorithm is recursive should not
inherently demand that the algorithm is also slow and excessively
wasteful, which is how I read the above. Yes, recursive algorithms can
have a higher overhead through function calls and stack usage, but this
isn't necessarily what should happen just because an algorithm is
recursive.
>
> 'Stack' is always of 'a limited size' because every computer has only
> a finite amount of memory. This has nothing to do with
> 'processors'. Depending on the environment, stack may well be very
> limited, eg when code is part of a Linux-kernel configured to use 4K
> per-thread stacks.
Agreed, I was using sloppy terminology here. My meaning was that for
many commonly used systems and user-level applications the amount of
stack space available to the system is large enough to that very deeply
non-tail recursive, non-optimized algorithms generally don't have too
much trouble, IME.
>
> Every algorithm using a loop with a finite number of iterations can be
> expressed recursively. No computer algorithm can ever be 'natural',
> because it is something completely artifical made by man (the same is
> more generally true for 'everything mathematic', this being another
> thing invented by man).
Using this definition, than yes, I agree. And, yes, iteration and
recursion can substitute each other, but that doesn't mean that one is
as simple or intuitive to implement as the other for a given problem.
>
> This is bollocks. Tail-recursive algorithms can be translated to
> iterative algorithms very easily, and some compilers occasionally do
> so automatically. This is a very important part of the job of an
> so-called 'optimizing compiler': Detect parts of an implementation
> which only exist because of some programmer delusion and replace them
> with more sensible variants.
>
> Because tail-recursive algorithms can easily be translated into
> iterative algorithms, they are 'use of recursion for the sake of using
> recursion' and should be avoided.
I disagree. For some compilers, the compiler is capable of generating
more efficient code from a recursively defined algorithm that it can
optimize, which utilizes little in the way of explicit assignments, than
can the equivalently easy to write iterative algorithm. It may be
possible to make the two equal in total efficiency at the end, but some
problems are easier to understand in the source code when reading and
writing them if they are written recursively.
Specifically, in my experience, certain compilers do a better job of
optimizing code which is written in a recursive, functional style, than
it does optimizing the equivalent code writen in an imperative,
assignment based iterative style. Thus, if the OP happens to be using
such a compiler, then it may be better to use a recursive style as
opposed to the iterative one.
Recursion, imo, should not be avoided simply because you can solve a
problem iteratively, but the method to use should be chosen on the basis
of what is more readable and maintainable and/or easier to write.
>
> Depending on the 'mental universe' someone programming a computer
> lives in, it may be more easy for him to use either recursion or
> iteration.
True, and since this is the case, I think that silly rules like, ``avoid
recursion as much as possible,'' should be thrown away, since usually
the choice of recursion vs. iteration isn't such a big problem, and it's
more important for the programmer to write ``intuitive'' code, for some
rough definition of intuitive.
>
> A not entirely unreasonable definition of 'insignificant difference'
> would be 'a difference someone doesn't care about'. Which means
> nothing except that someone doesn't care for the difference.
Yes. The point I was trying to make is that the gospel preaching of
``avoid recursion because it's too expensive'' is wrong, and shouldn't
be accepted as a coding guideline. Rather, code should be evaluated on
the actual results, and the results judged for what they are, without
the restrictive and relatively useless bias against recursion.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Rainer Weikusat 2008-03-11, 8:13 am |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>
> However, saneman says, ``should be slow,'' and this simply isn't
> true.
It simply is true.
> The simple fact that an algorithm is recursive should not inherently
> demand that the algorithm is also slow and excessively wasteful,
> which is how I read the above. Yes, recursive algorithms can have a
> higher overhead through function calls and stack usage, but this
> isn't necessarily what should happen just because an algorithm is
> recursive.
The 'simple fact' that an algorithm uses recurring subroutine calls
necessitates that it has both a higher speed and space overhead than
an equivalent algorithm not using recurring subroutine calls. This is
not something which 'the algorithm can have', because if it hasn't, it
isn't recursive.
[...]
>
> Using this definition, than yes, I agree. And, yes, iteration and
> recursion can substitute each other, but that doesn't mean that one is
> as simple or intuitive to implement as the other for a given
> problem.
What you consider to be 'simple' and 'intuitive' depends on you. Eg
most people without a CS background will certainly always consider
loops to be more simple and intuitive, for the simple reason that they
don't know anything except loops. People with a background in
functional programming will always consider recursion to be more
'simple and intuitive' because they are typically used to a language
which cannot express changes to complex objects over time. It is
meaningless to claim that one viewpoint would be 'right' and the other
'wrong': They are just different.
[...]
>
> I disagree. For some compilers, the compiler is capable of generating
> more efficient code from a recursively defined algorithm that it can
> optimize, which utilizes little in the way of explicit assignments, than
> can the equivalently easy to write iterative algorithm.
I was making a statement about tail recursion. Your statement is not
about tail recursion. Indepedently of this, it means little more than
'sometimes, something desirable could happen under certain
circumstance, whiles omething less desirable could happen if the
circumstances were different'. This can be reduced to Peter Frampton's
ingenious observation that 'something's happening all the time' :->.
Getting back to tail recursions, a recursive algorithm which some
compiler translates to an iterative algorithm is not a recursive
algorithm at the state of execution any more.
[...]
> Specifically, in my experience, certain compilers do a better job of
> optimizing code which is written in a recursive, functional style, than
> it does optimizing the equivalent code writen in an imperative,
> assignment based iterative style.
That the recursive description offers more possibilities for
improvment than an iterative description would is not exactly an
argument in favour of the former.
[...]
>
> Yes. The point I was trying to make is that the gospel preaching of
> ``avoid recursion because it's too expensive'' is wrong, and shouldn't
> be accepted as a coding guideline.
The alternate gospel "use recursion, because we math heads don't
understand time" isn't any better :->. Try cooking a meal recursively
:->>.
| |
| Aaron Hsu 2008-03-11, 10:16 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
> Getting back to tail recursions, a recursive algorithm which some
> compiler translates to an iterative algorithm is not a recursive
> algorithm at the state of execution any more.
Okay, so I think we understand each other. I am not talking about the
state of execution. I agree with you that at the level of machine code,
recursion can and usually does incur additional penalties on most
hardware. However, I am not talking about the eventual machine code
generated by a compiler, but rather, how the algorithms are expressed at
a high level in a given language that a programmer is going to use. That
programmer ought to be able to rely to some large extent on the ability
of the compiler to understand whatever means he uses, and then generate
the fastest code possible.
Thus, a programmer should not have to worry about using recursion inside
his code (usually) because the compiler ought to ensure that any
inefficiences are optimized away at the machine level.
>
> The alternate gospel "use recursion, because we math heads don't
> understand time" isn't any better :->. Try cooking a meal recursively
> :->>.
Agreed. So let's let the OP decide which is better for a given task at
hand, and not insist that one method should be used over the other, or
that one is more efficient than the other in the presence of good
compilers.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Scott Lurndal 2008-03-11, 10:16 pm |
| Aaron Hsu <arcfide@sacrideo.us> writes:
>Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>
>
>Okay, so I think we understand each other. I am not talking about the
>state of execution. I agree with you that at the level of machine code,
>recursion can and usually does incur additional penalties on most
>hardware.
I think you'll find that modern microprocessors have several optimizations
internally to make recursion much more efficient that it would have been
just a decade ago. For example, the processors will remember internally
some number of return addresses so it's not necessary to access a cache-line
or memory when implementing the RET instruction. Parameters are passed in
registers (and with x86 64-bit mode, at least the first six parameters will be
register-based).
For example, a call on the AMD Barcelona (Family 10h) processor takes
3 to 4 clocks, while the return takes 4 clocks. Each is faster than
or the same latency as a single 64-bit multiply instruction or a
move from memory to a register. [Source: Software Optimization
Guide for AMD Family 10h Processors, document number 40546 Rev 3.04]
You will dirty more cache-lines for the activation records on the stack,
but a single cache line will store up to 8 activation records (depending
on argument count and automatic storage allocation).
Recursive algorithms are often considered better from an implementation,
readability and maintenance standpoint as well; when the operation being
implemented is naturally recursive (e.g. recursive descent parsing).
scott
| |
| Aaron Hsu 2008-03-11, 10:16 pm |
| scott@slp53.sl.home (Scott Lurndal) writes:
> Recursive algorithms are often considered better from an implementation,
> readability and maintenance standpoint as well; when the operation being
> implemented is naturally recursive (e.g. recursive descent parsing).
I think this is the material point. Most programmers should be looking
at things from this angle, and should be relying on other programmers
who look at it from a hardware angle in order to build good compilers,
which the first class of programmer will then use as per the above.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Rainer Weikusat 2008-03-12, 8:12 am |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>
>
> Okay, so I think we understand each other.
Nope.
> I am not talking about the state of execution.
Then you are not talking about recursive algorithms, either, and
actually, you aren't even talking about algorithms at all.
| |
| Rainer Weikusat 2008-03-12, 8:12 am |
| scott@slp53.sl.home (Scott Lurndal) writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
> I think you'll find that modern microprocessors have several
> optimizations internally to make recursion much more efficient that
> it would have been just a decade ago.
In plain English, this means that 'so-called "modern" PC-processors
are finally starting to catch up with much older RISC chips wrt to
supporting efficient subroutine linkage'[*]. But this is a side remark
which doesn't touch the topic of the discussion at all. A subroutine
call, no matter how subroutine linkage works on some CPU, has
an inherent overhead associated with it and not doing a subroutine
call avoids this overhead.
[*] This was, of course, an optimistic statement which
happened to be completely wrong: The are only enhancments
for 'branch-predicting' return targets.
[...]
> Recursive algorithms are often considered better from an implementation,
> readability and maintenance standpoint as well;
Depending on whom you ask, recursive algorithms are often considered
worse from an implementation readability and maintenance standpoint,
too. Eg, I have met people using the term roughly synonymous to
'something horribly complicated which has gotten completely out of
control and will fail catastrophically really fast'.
| |
| Aaron Hsu 2008-03-12, 7:31 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
[...]
[color=darkred]
>
> Then you are not talking about recursive algorithms, either, and
> actually, you aren't even talking about algorithms at all.
Alright, then what am I talking about? Are you going to tell me that the
only reasonable domain to use when talking about algorithms is what is
actually on the machine code and not the actual source code that is
being used to generate that machine code?
I really am  here, because you seem to be talking about
recursive algorithms as if they were actually *on* a machine. However,
algorithms themselves are not machine code. They are processes of doing
things, and they don't have to be tied to any given machine
architecture. And, how we choose to express any given algorithm, can be
in an iterative or a recursive manner. At this level, the running time
of one function is not inherently slower than another, because we can't
and shouldn't know how they are going to be generated into machine
code. Once we have a simple expression for our algorithm, whether
iterative or recursive, then we can consider how this is generated into
machine code given our specific architecture(s) and our specific
compiler/interpreter. At that point, there are two many variables to
actually be able to say one way or the other whether our algorithms
which we expressed in source code using either recursive or iterative
constructs is going to be faster than the others expressed in the
opposing manner.
For example, let's take factorial. The following are three different
definitions for factorial:
(define (factorial-do n)
(do ([i 2 (1+ i)] [res 1 (* res i)])
([= i n] [* res i])))
(define (factorial-let n)
(let loop ([i 2] [res 1])
(if (= i n) (* res i) (loop (1+ i) (* res i)))))
(define (factorial-rec n)
(if (= n 1) 1 (* n (factorial-rec (1- n)))))
Here, FACTORIAL-DO and FACTORIAL-LET have almost the same execution
speed at about 29 seconds for calculating 100000! with minimal
optimizations. FACTORIAL-REC takes about 41 seconds to do the same
thing. FACTORIAL-LET and FACTORIAL-REC both use recursion to express the
algorithm. However, the way that FACTORIAL-LET uses recursion is done in
such a way that it is trivial for the compiler to reduce function call
overhead even at low optimization levels. Some peole argue that
FACTORIAL-LET is really an iterative algorithm at its heart, and that
could be true, but it is still *expressed* using recursion.
Freedom and clarity of expression is usually more favorable for most
projects and in most areas of projects than is speed, and so, even if an
algorithm is coded recursively in such a way that it is slower on the
executing machine using a given compiler, it may be very well worth it.
The point is that recursive algorithms (used in the machine-independent
sense of that phrase) are not inherently less efficient, and may or may
not be more readable, maintainable, &c. Therefore, we should not teach
students to avoid recursion but should teach them to examine different
methods of doing something, and see what works best for them in terms of
readability, maintainability and speed in so far as each of these is
important to the task at hand.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Aaron Hsu 2008-03-12, 7:31 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> scott@slp53.sl.home (Scott Lurndal) writes:
>
>
> Depending on whom you ask, recursive algorithms are often considered
> worse from an implementation readability and maintenance standpoint,
> too. Eg, I have met people using the term roughly synonymous to
> 'something horribly complicated which has gotten completely out of
> control and will fail catastrophically really fast'.
It is my experience that most of the people who have such feelings about
recursion are those people who don't understand how or when to use
it. They are usually people who don't *really* have a strong grasp on
the theoretical side of Computer Science. I rarely meet a highly
educated computer scientist who has a full or very strong grasp of
both recursion and iteration that dislikes recursion. Most of them I
meet actually make it a point to promote recursion as a very nice
solution to problems. Those who don't like it usually don't like it
because their specific problem domain doesn't permit them to make use of
it well, and so they have no use for it; they don't dislike it, they
just can't use it well in their work.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Aaron Hsu 2008-03-12, 7:31 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> scott@slp53.sl.home (Scott Lurndal) writes:
>
>
> Depending on whom you ask, recursive algorithms are often considered
> worse from an implementation readability and maintenance standpoint,
> too. Eg, I have met people using the term roughly synonymous to
> 'something horribly complicated which has gotten completely out of
> control and will fail catastrophically really fast'.
It is my experience that most of the people who have such feelings about
recursion are those people who don't understand how or when to use
it. They are usually people who don't *really* have a strong grasp on
the theoretical side of Computer Science. I rarely meet a highly
educated computer scientist who has a full or very strong grasp of
both recursion and iteration that dislikes recursion. Most of them I
meet actually make it a point to promote recursion as a very nice
solution to problems. Those who don't like it usually don't like it
because their specific problem domain doesn't permit them to make use of
it well, and so they have no use for it; they don't dislike it, they
just can't use it well in their work.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Rainer Weikusat 2008-03-12, 7:31 pm |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>
> [...]
>
>
> Alright, then what am I talking about?
Things you heard elsewhere and have chosen to repeat without thinking
about them, most likely, because they had sufficent organizational
authority attached to it that this seemed to be a wise course of
action.
It needs a particularly arrogant XXXXXXX to actually demand that only
people with 'a sufficient grasp of theoretical computer science' (aka
'a sufficient graps about discrete mathematics desperatelty trying to
pretend to be useful) should be able to make any use of computers.
Tell this to your professor if you ever feel like a person.
| |
| Rainer Weikusat 2008-03-12, 7:31 pm |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>
>
> [...]
>
>
> Alright, then what am I talking about?
Things you have heard elsewhere, repeating them without much thought.
> Are you going to tell me that the only reasonable domain to use when
> talking about algorithms is what is actually on the machine code and
> not the actual source code that is being used to generate that
> machine code?
The only reasonable to domain when talking about algorithms is
actually talking about algorithms, not about 'some unspecified other
procedure the magic device constructed by the much wiser people will
certainly substitute for the one I came up with'.
Coming up with some at all usable procedure description is only the
first-level problem.
| |
| Aaron Hsu 2008-03-12, 10:24 pm |
| Rainer Weikusat <rweikusat@mssgmbh.com> writes:
> Aaron Hsu <arcfide@sacrideo.us> writes:
>
> Things you heard elsewhere and have chosen to repeat without thinking
> about them, most likely, because they had sufficent organizational
> authority attached to it that this seemed to be a wise course of
> action.
At this point you've ceased making any applicable point. I am curious to
know in your mind how you deal with the theoretical discussion of
algorithms outside of the specific hardware on which they are
implemented. It is VERY reasonable to speak about computation and the
methods of computation outside of actual physical hardware. If you think
we can only discuss recursion and iteration on the level of a machine to
run it on, and that algorithms must necessarily be thought of only in
terms of what happens on the machine, then you are wrong.
> It needs a particularly arrogant XXXXXXX to actually demand that only
> people with 'a sufficient grasp of theoretical computer science' (aka
> 'a sufficient graps about discrete mathematics desperatelty trying to
> pretend to be useful) should be able to make any use of computers.
I agree. You'd have to be pretty arrogant to make the claim that someone
has to understand computer science to be able to make any use of
computers. You'll also agree with me, then, when I point out that I did
not say this.
--
Aaron Hsu <arcfide@sacrideo.us> | Jabber: arcfide@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
| |
| Rainer Weikusat 2008-03-13, 8:16 am |
| Aaron Hsu <arcfide@sacrideo.us> writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
[...]
[color=darkred]
>
> At this point you've ceased making any applicable point.
The applicable point would be that you continue to post superficially
thought-out 'boilerplate nonsense', using some parts of the texts I
wrote as platform to place them on, ignoring whatever doesn't appear
to be suitable for doing so, as continously just passing over anything
which could be considered to be relevant detail. Unsubstantiated
theories about 'how to world ought to look like', as opposed to how it
actually does, belong into the realm of either philosophy or religion.
> I am curious to know in your mind how you deal with the theoretical
> discussion of algorithms outside of the specific hardware on which
> they are implemented.
No 'specific hardware' had been mentioned so far.
> It is VERY reasonable to speak about computation and the
> methods of computation outside of actual physical hardware.
It is not reasonable and actually, not even possible, to discuss
'algorithms', ie formalized descriptions of procedures intended to
accomplish certain things, without actually refering to the steps
the procedure itself is composed of.
> If you think we can only discuss recursion and iteration on the
> level of a machine to run it on, and that algorithms must
> necessarily be thought of only in terms of what happens on the
> machine, then you are wrong.
I'd suggest that you discuss this with the person whose idea it is:
http://www-cs-faculty.stanford.edu/~uno/index.html
And maybe publish at least one larger book on the topic being widelay
recognized as 'seminal'.
|
|
|
|
|