Questa funzione indica il suo calcolo x = (x-1) + x ^ 2?
Function unknown(x)
if ( x == 1 )
return 1
else
return unknown(x‐1) + x*x
La funzione può essere scritta in una forma più matematica come:
unknown(1) = 1
unknown(x) = unknown(x - 1) + x * x [if x is not 1]
Per capire perché questo è uguale alla somma dei quadrati, puoi sostituire la seconda linea in sé in modo ricorsivo e osservare il modello che emerge:
unknown(x) = unknown(x - 1) + x * x
unknown(x) = unknown(x - 2) + (x - 1) * (x - 1) + x * x
unknown(x) = unknown(x - 3) + (x - 2) * (x - 2) + (x - 1) * (x - 1) + x * x
etc ...
Dopo aver espanso più volte, alla fine si scopre che * si raggiungerà il caso speciale di unknown(1) poiché l'argomento diminuisce costantemente di uno a ogni espansione. Quindi,
(after expanding many times ...)
unknown(x) = unknown(1) + 2 * 2 + ... + (x - 1) * (x - 1) + x * x
unknown(x) = 1 + 2 * 2 + ... + (x - 1) * (x - 1) + x * x
Quindi, questa è semplicemente la somma dei quadrati .
[*] A meno che il tuo x iniziale sia minore di uno, nel qual caso la funzione diverge (non termina mai) poiché l'argomento continuerà a diventare sempre più negativo.
Bene calcola ricorsivamente x2 + (x-1)2 + (x-2)2 + ⋯ + 22 + 1 .
Questa è la somma dei quadrati dei numeri naturali. La somma dei primi n di numeri naturali può essere rappresentata matematicamente da:
n*(n+1)*(2n+1)/6
Leggi altre domande sui tag recursion algorithms