-1

Possible Duplicate:
Recursion and Iteration

What is the difference between a recursive and a non-recursive function? Fibonacci to be exact.

I looking for answers that relate towards the time and memory.

Community
  • 1
  • 1
dalawh
  • 886
  • 8
  • 15
  • 37
  • 3
    Recursive functions call recursive functions. – raina77ow Oct 17 '12 at 16:42
  • @raina77ow, ok, but this is just because recursive functions invoke themselves, directly or indirectly. – TheBlastOne Oct 17 '12 at 16:44
  • 2
    What you are asking is the difference between a recursion and iteration...it's already answered many times on SO, http://stackoverflow.com/questions/72209/recursion-or-iteration and http://stackoverflow.com/questions/2576993/recursion-and-iteration and http://stackoverflow.com/questions/2185532/why-should-recursion-be-preferred-over-iteration – Arham Oct 17 '12 at 16:54

2 Answers2

1

"Recursive" simply means that a function calls itself. This may or may not be intentional (unintentional recursion is responsible for lots of crashes).

Intentional recursion, where a function performs part of an operation, then calls itself to perform the remaining part, is often a useful programming paradigm, but requires some degree of comprehension/experience/skill to "get your head around it".

Basically, recursion can be used to replace "iteration" (loops) and to replace accompanying array allocations (with variables local to the function body). But not every iterative or array-using function can be effectively converted to its recursive equivalent.

If the problem is suitable for recursion, one can often write a recursive version that is about equivalent in execution efficiency to the non-recursive version ... maybe slightly better or worse depending on how efficient the call mechanism is compared to looping and array indexing in the language/compiler. In terms of storage, recursion is rarely more efficient, but it benefits from not having to pre-allocate (and pre-know the size of the allocation) for the particular problem at hand.

Mostly recursion is better (when it actually is) because it makes an implementation much simpler and less error-prone, and errors are by far the biggest cost in computing. (But of course improperly done it can cost you big time as well.)

When recursion is good it's very good. When recursion is bad it's very bad.

Hot Licks
  • 47,103
  • 17
  • 93
  • 151
  • So time is not affected? How about memory? – dalawh Oct 17 '12 at 20:17
  • Both are affected, it's just that the effect is unpredictable. In the simple case memory is much higher for recursion, since there's a stack frame overhead with each call. But for complex cases the need to allocate large arrays "just in case" is eliminated. – Hot Licks Oct 17 '12 at 21:01
0

Recursive functions are procedures or subroutines implemented in a programming language, whose implementation references itself.

Non Recursive Function are procedures or subroutines implemented in a programming language, whose implementation does not references itself

Below is a link for recursive and non recursive fibonacci series:- Recursive and Non Recursive Fibonacci Series

Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
  • Ok, now tell me: are these - `function a(x) { return x ? b(x-1) : 0; } function b(x) { return x ? a(x-1) : 0; }` - recursive? – raina77ow Oct 17 '12 at 16:45
  • I disagree. I can develop a function written in a given programming language, which calls a function written in a different programming language, and both implementations reference the "other" function. Result: Recursive references, not visible in each function's implementation. It's an indirect recursion. – TheBlastOne Oct 17 '12 at 16:46
  • @raina77ow, correct, you don´t even have to use different languages. Recursive. Indirectly. – TheBlastOne Oct 17 '12 at 16:47