Nozioni di base sulla ricorsione in Python

Question

"Scrivi una funzione ricorsiva," listSum "che accetta un elenco di numeri interi e restituisce la somma di tutti gli interi nell'elenco".

Esempio:

>>>> listSum([1,3,4,5,6]) 
19 

so come farlo in un altro modo, ma non nel modo ricorsivo.

def listSum(ls): 
    i = 0 
    s = 0 
    while i < len(ls): 
     s = s + ls[i] 
     i = i + 1 
    print s 

Ho bisogno del modo di base per farlo poiché non sono consentite funzioni speciali integrate.

Answer 1

Ogni volta che dovete affrontare un problema come questo, cercare di esprimere il risultato della funzione con la stessa funzione.

Nel tuo caso, puoi ottenere il risultato aggiungendo il primo numero con il risultato di chiamare la stessa funzione con il resto degli elementi nell'elenco.

Per esempio,

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) 
         = 1 + (3 + listSum([4, 5, 6])) 
         = 1 + (3 + (4 + listSum([5, 6]))) 
         = 1 + (3 + (4 + (5 + listSum([6])))) 
         = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

Ora, quello che dovrebbe essere il risultato di listSum([])? Dovrebbe essere 0. Si chiama condizione di base della tua ricorsione. Quando viene soddisfatta la condizione di base, la ricorsione terminerà. Ora, proviamo a implementarlo.

La cosa principale qui è dividere l'elenco. È possibile utilizzare slicing per farlo.

Semplice versione

>>> def listSum(ls): 
...  # Base condition 
...  if not ls: 
...   return 0 
... 
...  # First element + result of calling `listsum` with rest of the elements 
...  return ls[0] + listSum(ls[1:]) 
>>> 
>>> listSum([1, 3, 4, 5, 6]) 
19 

---

coda Chiamata ricorsione

Una volta capito come funziona il ricorsione di cui sopra, si può provare a fare un po 'meglio. Ora, per trovare il risultato effettivo, dipendiamo anche dal valore della funzione precedente. L'istruzione return non può restituire immediatamente il valore finché la chiamata ricorsiva non restituisce un risultato. Possiamo evitare questo, passando la corrente al parametro funzionale, come questo

>>> def listSum(ls, result): 
...  if not ls: 
...   return result 
...  return listSum(ls[1:], result + ls[0]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0) 
19 

Qui, passiamo quale valore iniziale della somma sia nei parametri, che è zero nel listSum([1, 3, 4, 5, 6], 0). Quindi, quando viene soddisfatta la condizione di base, stiamo effettivamente accumulando la somma nel parametro result, quindi la restituiamo. Ora, l'ultima istruzione return ha listSum(ls[1:], result + ls[0]), dove aggiungiamo il primo elemento all'attuale result e lo passiamo nuovamente alla chiamata ricorsiva.

Questo potrebbe essere un buon momento per capire Tail Call.Non sarebbe rilevante per Python, in quanto non ottimizza le chiamate tail.

---

passando intorno versione indice

Ora, si potrebbe pensare che stiamo creando tante liste intermedi. Posso evitarlo?

Naturalmente, è possibile. Hai solo bisogno dell'indice dell'articolo da elaborare successivamente. Ma ora, le condizioni di base saranno diverse. Dal momento che stiamo per passare l'indice, come determineremo come è stato elaborato l'intero elenco? Bene, se l'indice è uguale alla lunghezza della lista, allora abbiamo elaborato tutti gli elementi in essa contenuti.

>>> def listSum(ls, index, result): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6], 0, 0) 
19 

---

funzione interna versione

Se si guarda la definizione della funzione ora, si passa tre parametri ad esso. Diciamo che rilascerai questa funzione come un'API. Sarà conveniente che gli utenti passino tre valori, quando effettivamente trovano la somma di una lista?

No. Cosa possiamo fare a riguardo? Possiamo creare un'altra funzione, che è locale alla funzione attuale listSum e possiamo passare tutti i parametri relativi implementazione per esso, come questo

>>> def listSum(ls): 
... 
...  def recursion(index, result): 
...   if index == len(ls): 
...    return result 
...   return recursion(index + 1, result + ls[index]) 
... 
...  return recursion(0, 0) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

Ora, quando il listSum si chiama, semplicemente restituisce il valore di ritorno di recursion funzione interna, che accetta i parametri index e result. Ora stiamo trasmettendo solo quei valori, non gli utenti di listSum. Devono solo passare la lista per essere processati.

In questo caso, se si osservano i parametri, non si passa ls a recursion ma lo stiamo utilizzando al suo interno. ls è accessibile all'interno di recursion a causa della proprietà di chiusura.

---

parametri di default della versione

Ora, se si vuole mantenere le cose semplici, senza creare una funzione interna, è possibile utilizzare i parametri di default, come questo

>>> def listSum(ls, index=0, result=0): 
...  # Base condition 
...  if index == len(ls): 
...   return result 
... 
...  # Call with next index and add the current element to result 
...  return listSum(ls, index + 1, result + ls[index]) 
... 
>>> listSum([1, 3, 4, 5, 6]) 
19 

Ora, se il chiamante non passa esplicitamente alcun valore, allora 0 verrà assegnato a entrambi gli standard index e result.

---

ricorsivo problema di alimentazione

Ora, consente di applicare le idee per un problema diverso. Ad esempio, proviamo ad implementare la funzione power(base, exponent). Restituirebbe il valore di base elevato alla potenza exponent.

power(2, 5) = 32 
power(5, 2) = 25 
power(3, 4) = 81 

Ora, come possiamo farlo in modo ricorsivo? Cerchiamo di capire come vengono raggiunti questi risultati.

power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 
power(5, 2) = 5 * 5    = 25 
power(3, 4) = 3 * 3 * 3 * 3  = 81 

Hmmm, quindi abbiamo capito. Il base moltiplicato per se stesso, exponent volte dà il risultato. Ok, come ci avviciniamo. Cerchiamo di definire la soluzione con la stessa funzione.

power(2, 5) = 2 * power(2, 4) 
      = 2 * (2 * power(2, 3)) 
      = 2 * (2 * (2 * power(2, 2))) 
      = 2 * (2 * (2 * (2 * power(2, 1)))) 

Quale dovrebbe essere il risultato se qualcosa viene sollevato per alimentare 1? Il risultato sarà lo stesso numero, giusto? Abbiamo ottenuto le nostre condizioni di base per la nostra ricorsione :-)

  = 2 * (2 * (2 * (2 * 2))) 
      = 2 * (2 * (2 * 4)) 
      = 2 * (2 * 8) 
      = 2 * 16 
      = 32 

OK, consente di implementarlo.

>>> def power(base, exponent): 
...  # Base condition, if `exponent` is lesser than or equal to 1, return `base` 
...  if exponent <= 1: 
...   return base 
... 
...  return base * power(base, exponent - 1) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

Va bene, come sarà definire la chiamata in coda ottimizzata versione di esso? Consente di passare il risultato corrente come parametro alla funzione stessa e restituire il risultato quando la condizione di base è soddisfatta. Manteniamolo semplice e utilizzare direttamente l'approccio parametrico predefinito.

>>> def power(base, exponent, result=1): 
...  # Since we start with `1`, base condition would be exponent reaching 0 
...  if exponent <= 0: 
...   return result 
... 
...  return power(base, exponent - 1, result * base) 
... 
>>> power(2, 5) 
32 
>>> power(5, 2) 
25 
>>> power(3, 4) 
81 

Ora, riduciamo il valore exponent in ogni chiamata ricorsiva e multiple result con base e passarlo al ricorsivo power chiamata. Iniziamo con il valore 1, perché ci stiamo avvicinando al problema al contrario. La ricorsione avverrà come questo

power(2, 5, 1) = power(2, 4, 1 * 2) 
       = power(2, 4, 2) 
       = power(2, 3, 2 * 2) 
       = power(2, 3, 4) 
       = power(2, 2, 4 * 2) 
       = power(2, 2, 8) 
       = power(2, 1, 8 * 2) 
       = power(2, 1, 16) 
       = power(2, 0, 16 * 2) 
       = power(2, 0, 32) 

Dal exponent diventa zero, la condizione di base è soddisfatta e verrà restituito il result, in modo da ottenere 32 :-)

Answer 2

L'uscita anticipata è tipica delle funzioni ricorsive. seq è falsa quando vuoto (quindi quando non ci sono numeri lasciati per sommare).

La sintassi della sezione consente di passare la sequenza alla funzione chiamata in modo ricorsivo senza il numero intero consumato nel passaggio corrente.

def listSum(seq): 
    if not seq: 
     return 0 
    return seq[0] + listSum(seq[1:]) 

print listSum([1,3,4,5,6]) # prints 19 

Answer 3

def listSum(L): 
    """Returns a sum of integers for a list containing 
    integers. 
    input: list of integers 
    output: listSum returns a sum of all the integers 
    in L. 
    """ 
    if L == []: 
     return [] 
    if len(L) == 1: 
     return L[0] 
    else: 
     return L[0] + listSum(L[1:]) 
print listSum([1, 3, 4, 5, 6]) 
print listSum([]) 
print listSum([8])