difference between recursive and iterative

This is a discussion on difference between recursive and iterative within the C Programming forums, part of the General Programming Boards category; Originally Posted by Salem Only the most perverse coder would have a recursive strlen() function for example I guess this ...

  1. #16
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by Salem
    Only the most perverse coder would have a recursive strlen() function for example
    I guess this would include quite a few lecturers from the university I attend(word?) to Especially those with a functional language background like Scheme.


    The difference between a recursive and an interative function isn't always clear. For one, a function that calls itself doesn't always have to be a recursive function. Usually a recursive algorithm doesn't produce any kind of result until the last layer of recursion is reached. Once this happens, the "real" calculations begin - backwards.

    Consider f: f(x)= { 0 for x==0; f(x -1) +1 otherwise }

    Code:
        f(4) =>
        f(3) +1 =>
       (f(2) +1) +1 =>
      ((f(1) +1) +1) +1 =>
     (((f(0) +1) +1) +1) +1 =>
        0  +1  +1  +1  +1 = 4
    As you can see, a real stack is built but nothing is known about the result until the bottom is hit. This is a recursive function.

    This one is - strictly speaking - not recursive, although it calls itself:

    Code:
     int iter_main(int x) {
       int iter_sub(int i, int j) {
      	if (j-- <= 0)
      	  return i;
      	else
       	 return iter_sub(i++, j);
       }
       return iter_sub(0, x);
     }
    I admit, it's not really apparent. It's late here and I couldn't come up with something better

    (I didn't test it - hopefully there are not typos in it.)

  2. #17
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Any function that calls itself is recursive. It doesn't matter what the end result is. For that matter, you can have a void function that does no computation, and it still would be recursive if it calls itself. That by definition is recusion: A function that calls itself.
    definition:
    <mathematics, programming> When a function (or procedure)
    calls itself. Such a function is called "recursive".
    If the
    call is via one or more other functions then this group of
    functions are called "mutually recursive".

    If a function will always call itself, however it is called,
    then it will never terminate. Usually however, it first
    performs some test on its arguments to check for a "base case"
    - a condition under which it can return a value without
    calling itself.
    Quzah.
    Hope is the first step on the road to disappointment.

  3. #18
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >This one is - strictly speaking - not recursive, although it calls itself
    Strictly speaking, it isn't recursive because it wouldn't compile and thus wouldn't run. Therefore, it would never call itself because the first call is impossible.
    My best code is written with the delete key.

  4. #19
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by Prelude
    >This one is - strictly speaking - not recursive, although it calls itself
    Strictly speaking, it isn't recursive because it wouldn't compile and thus wouldn't run. Therefore, it would never call itself because the first call is impossible.
    Strictly speaking, it does compile.

  5. #20
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Strictly speaking, it does compile.
    Then strictly speaking, you aren't compiling C. Nested functions are illegal in standard C, they always have been.
    My best code is written with the delete key.

  6. #21
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Iteration is tail recursion,. Any iterative function can also be done recursive, and languages like scheme do not have iteration as a core language feature.

  7. #22
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    I think Nyda is using the scheme terminolgy. It is a purer definition because this describes the process of computation and not the program.

  8. #23
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by Prelude
    >Strictly speaking, it does compile.
    Then strictly speaking, you aren't compiling C. Nested functions are illegal in standard C, they always have been.
    It requires a GCC at highest warning level, pedantic, to complain about this. Anyway, I'm pretty certain you could figure out what the function was supposed to do, Prelude, even if your brain powered compiler doesn't yet support nested functions :-)

    quzah, where did you dig that definition out? Just calling itself doesn't make it recursive. I remember we had to tell recursive from iterative in one of the first computer science semesters.

  9. #24
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Nyda, if you have the book, go read the sicp explanation. Note also that these definitions are not what C programmers use because we call recursive what follows the language standard, and we use tail recursive to mean a recursive function for an iterative algorithm.

  10. #25
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    Quote Originally Posted by okinrus
    Nyda, if you have the book, go read the sicp explanation. Note also that these definitions are not what C programmers use because we call recursive what follows the language standard, and we use tail recursive to mean a recursive function for an iterative algorithm.
    I know this is a C board but the original author sounded like he wanted more than just the simplified standard answer for C programmers. Especially since he quoted a mathematical formula.
    Anyway, if the standard says recursive=selfcalling I'm fine with it. Thanks for pointing this out. I must admit this makes things a bit easier. That again is really strange, considering the fact we're talking about C :-)

  11. #26
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Nyda
    quzah, where did you dig that definition out? Just calling itself doesn't make it recursive. I remember we had to tell recursive from iterative in one of the first computer science semesters.
    Click the provided red link.

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,778
    That reference originally came from FOLDOC (though much of FOLDOC comes from esr's Jargon File):
    http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?recursive
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Goscinny or Uderzo?
    Join Date
    Jun 2004
    Posts
    33
    Just from a Mathematician's point of view (I've had to use The Newton Raphson formula countless times in the last few years in my research work in Molecular Dynamics):

    Newton Raphson is a recursive formula that is solved by iteration:
    The formula itself is recursive, but the process by which it is solved is iterative. By increasing the number or iterations, you increase the accuracy of the result due to the recursion.

    The recursion in this case is simply that results of a previous "iteration" are used as the input parameters for the following "iteration". Therefore, the results of each iteration are being used recursively within the formula.

    Newton-Raphson is a special case in that there is no minimum number of results required to get your answer (such as in a factorial calculation: a recursive formula solved by recursion). Newton-Raphson simply gets more accurate with each iteration.

    Recursion and iteration are related PROCESSES. Recursive and iterative are descriptive of their associated properties. Recursion may be considered to be a special case of iteration. e.g. A factorial calculation has a fixed number of calls to itself. 3 factorial is always going to be
    3*(3-1)= 6
    6*(2-1)=12
    No increase in the number of operations performed will increase the accuracy (ignoring computer accuracy). This is a recursion.

    A recursion has a fixed endpoint (dependent on the initial input). Newton-Raphson does not.

    The formula is "recursive" (it has recursive properties in that it calls itself). It is solved by iteration (you can vary the number of operations performed and still have a more or less correct result).

    Hope this helps.
    Last edited by Tankndozer; 07-05-2004 at 04:34 AM.

  14. #29
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >It requires a GCC at highest warning level, pedantic, to complain about this.
    That's because -pedantic rejects GCC extensions that standard C forbids. It doesn't mean that C allows nested functions.

    >Anyway, I'm pretty certain you could figure out what the function was supposed to do, Prelude
    I knew what you meant, but that doesn't make it right.

    >even if your brain powered compiler doesn't yet support nested functions :-)
    My brain does support nested functions, it just happens to run lint too.
    My best code is written with the delete key.

  15. #30
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Thank you very much Tankndozer.
    I'm very pleased that this question caused such a very good and interesting discussion. I'm very satisfied with answers. I started to think about a lot of things that I didn't before.
    Maybe I need to explain how that question came upon my mind.
    I'm a student of electrical engineering. I was learning and preparing for exam and in one book that discuss experimental methods for analyzing control processes and found the following:

    "Based on the way how we processing aquired data about specific process we can divide ways of data processing to:
    - nonrecursive
    -recursive.
    In recursive processing we're calculating model of the process using values from previous steps and newly aquired data. Usually we use that newly aquired data to make model better representing a real process.

    Nonrecursive processing can be divided into:
    -direct
    -iterative.

    In direct processing we get model in one step.
    In iterative nonrecursive processing using which we get a model from more than one steps"

    I translate this as good as I can, so excuse any possible mistakes.

    This makes me think about difference between recursive and iterative methods.

    I know this is not specific for C programming, but question is really interesting. It depends on which point of view you observe problem.
    I must admit that using this board I've learned a lot, not only about C/C++ programming but also how to think, how to approach to specific problems.

    Thank you very much.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using both a Recursive and Iterative Functions
    By belkins in forum C Programming
    Replies: 12
    Last Post: 11-02-2008, 11:31 AM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  3. splitting linked list recursive vs. iterative
    By Micko in forum C Programming
    Replies: 7
    Last Post: 03-17-2005, 04:51 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Iterative Tree Traversal using a stack
    By BigDaddyDrew in forum C++ Programming
    Replies: 7
    Last Post: 03-10-2003, 04:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21