Is array dependence on previous terms considered recursive?

For example, take the case of Fibonacci number to calculate nth number you require `n-1` and `n-2` term.

If I do it with bottom up approach, is it recursion as `f(n)` depends on `f(n-1)`?

• It's recursive with memoization, I think. Commented Feb 20, 2014 at 5:47

There are several slightly different meanings to the term "recursive":

• The definition of Fibonacci sequence is recurrent. This is property of the definition, no matter how you implement it.
• The function to calculate it is totally recursive, i.e. computable.
• The implementation of the function is recursive if it actually calls itself. If you create the array manually and convert the recursion to a loop, it usually is not called recursive.

The bottom-up approach is (without unnecessarily wasting space for n values when last two is all that's required):

``````def fib(n):
f_2, f_1 = 0, 1
for _ in xrange(1, n):
f_2, f_1 = f_1, f_2 + f_1
return f_1
``````

and that's not recursive.

However any loop can be rewritten as recursive, which would look like:

``````def fib(n):
def f(n, f_2, f_1):
if n == 1:
return f_1
else:
return f(n, f_1, f_2 + f_1)
return f(n, 0, 1)
``````

It's getting somewhat convoluted by now though, but in functional languages (like Haskell) and mostly functional ones (like Lisp/Scheme) it would probably be the more natural definition. And in those languages with tail-recursion optimization (like Haskell or Scheme) it is just as efficient.

• To confuse matters even more: in a language with Proper Tail Calls, your latter procedure definition is recursive (or more precisely, tail-recursive), but calling it yields an iterative process. Commented Feb 20, 2014 at 12:00
• @JörgWMittag: Actually I initially had another version that was recursive, but not tail-recursive, but that would not qualify as bottom-up approach. The accumulator tail-recursive transformation of the loop fits that better. And while editing the note about tail-recursion slipped through the crack. Commented Feb 20, 2014 at 19:00

I would consider it "recursion" if you call a function calls itself.

Something like this:

``````f(n) {
....
return f(n-2) + f(n-1);
}
``````

You do the same thing with a loop and it wouldn't be recursion

``````f(n) {
.....
for ( i =2 ; i< n ;i++)
arr[i] = arr[i-1] + arr[i-2]
}
``````