La dipendenza dell'array dai termini precedenti è considerata ricorsiva?

Ci sono diversi significati leggermente diversi rispetto al termine "ricorsivo":

• La definizione della sequenza di Fibonacci è ricorrente . Questa è una proprietà della definizione, indipendentemente da come la si implementa.
• La funzione per calcolarlo è totalmente ricorsivo , cioè computabile.
• L'implementazione della funzione è ricorsiva se in realtà si chiama da sola. Se crei l'array manualmente e converti la ricorsione in un loop, di solito è non chiamato ricorsivo.

L'approccio bottom-up è (senza inutilmente sprecare spazio per n valori quando gli ultimi due sono tutto ciò che è richiesto):

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

e questo è non ricorsivo .

Tuttavia, qualsiasi loop può essere riscritto come ricorsivo, che dovrebbe apparire come:

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)

Ormai è piuttosto complicato, ma in linguaggi funzionali (come Haskell) e in gran parte funzionali (come Lisp / Scheme) probabilmente sarebbe la definizione più naturale. E in quelle lingue con ottimizzazione della ricorsione in coda (come Haskell o Scheme) è altrettanto efficiente.

Lo considererei "ricorsione" se chiami una funzione stessa.

Qualcosa del genere:

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

Fai la stessa cosa con un ciclo e non sarebbe una ricorsione

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