Thread: difference between recursive and iterative

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

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.

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.

I think Nyda is using the scheme terminolgy. It is a purer definition because this describes the process of computation and not the program.

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.

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.

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

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.