Books on recursive programming? - Unix

This is a discussion on Books on recursive programming? - Unix ; 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 ...

+ Reply to Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 21

Thread: Books on recursive programming?

  1. Books on recursive programming?

    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?


  2. Re: Books on recursive programming?

    saneman 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.

  3. Re: Books on recursive programming?

    saneman 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.

  4. Re: Books on recursive programming?

    saneman 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 ...).

  5. Re: Books on recursive programming?

    saneman 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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  6. Re: Books on recursive programming?

    Aaron Hsu writes:
    > saneman writes:


    [...]

    >> 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.


    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.

    >> 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 '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.

  7. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > Aaron Hsu writes:
    >> saneman writes:

    >
    > [...]
    >
    >>> 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.

    >
    > 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.

    >> 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.


    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.

    >> 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).


    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.

    >> 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.


    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.

    >>> 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 '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.

    >> 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.


    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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  8. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > Aaron Hsu writes:
    >> saneman writes:

    >
    > [...]
    >
    >>> 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.

    >
    > 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.

    >> 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.


    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.

    >> 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).


    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.

    >> 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.


    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.

    >>> 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 '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.

    >> 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.


    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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  9. Re: Books on recursive programming?

    Aaron Hsu writes:
    > Rainer Weikusat writes:
    >> Aaron Hsu writes:
    >>> saneman writes:

    >>
    >> [...]
    >>
    >>>> 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.

    >>
    >> 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.


    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.

    [...]

    >> 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.


    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.

    [...]

    >> 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.


    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.

    [...]

    >> 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.


    The alternate gospel "use recursion, because we math heads don't
    understand time" isn't any better :->. Try cooking a meal recursively
    :->>.

  10. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > Aaron Hsu writes:
    >> Rainer Weikusat writes:
    >>> Aaron Hsu writes:
    >>>> saneman 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.

    >>> 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.

    >
    > 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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  11. Re: Books on recursive programming?

    Aaron Hsu writes:
    >Rainer Weikusat writes:
    >
    >> Aaron Hsu writes:
    >>> Rainer Weikusat writes:
    >>>> Aaron Hsu writes:
    >>>>> saneman 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.


    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

  12. Re: Books on recursive programming?

    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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  13. Re: Books on recursive programming?

    Aaron Hsu writes:
    > Rainer Weikusat writes:
    >
    >> Aaron Hsu writes:
    >>> Rainer Weikusat writes:
    >>>> Aaron Hsu writes:
    >>>>> saneman 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.


    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.

  14. Re: Books on recursive programming?

    scott@slp53.sl.home (Scott Lurndal) writes:
    > Aaron Hsu writes:
    >>Rainer Weikusat writes:
    >>
    >>> Aaron Hsu writes:
    >>>> Rainer Weikusat writes:
    >>>>> Aaron Hsu writes:
    >>>>>> saneman 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.

    >
    > 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'.

  15. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > Aaron Hsu writes:
    >
    >> Rainer Weikusat 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.


    [...]

    >> 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.


    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 confused 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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  16. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > scott@slp53.sl.home (Scott Lurndal) writes:
    >
    >> 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'.


    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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  17. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > scott@slp53.sl.home (Scott Lurndal) writes:
    >
    >> 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'.


    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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

  18. Re: Books on recursive programming?

    Aaron Hsu writes:
    > Rainer Weikusat writes:
    >> Aaron Hsu writes:
    >>> Rainer Weikusat 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.

    >
    > [...]
    >
    >>> 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.

    >
    > 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 asshole 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.

  19. Re: Books on recursive programming?

    Aaron Hsu writes:
    > Rainer Weikusat writes:
    >
    >> Aaron Hsu writes:
    >>
    >>> Rainer Weikusat 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.

    >
    > [...]
    >
    >>> 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.

    >
    > 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.

  20. Re: Books on recursive programming?

    Rainer Weikusat writes:

    > Aaron Hsu writes:
    >> Rainer Weikusat writes:
    >>> Aaron Hsu writes:
    >>>> Rainer Weikusat 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.

    >>
    >> [...]
    >>
    >>>> 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.

    >>
    >> 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.


    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 asshole 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 | Jabber: arcfide@jabber.org
    ``Government is the great fiction through which everybody endeavors to
    live at the expense of everybody else.'' - Frederic Bastiat

+ Reply to Thread
Page 1 of 2 1 2 LastLast