[Java] Algoritmo ricorsivo stile colloquio Google

[absinth]

Ciao a tutti! Ho risolto un esercizio ma non so se la mia soluzione va bene perché non so se ho capito bene la ricorsione.

Consegna:
E' dato un array A[1..n] composto da n numeri reali arbitrari diversi da zero. Vogliamo calcolare un secondo
array B[1..n], in cui B = A[1] * A[2] * … * A[n] / A. Scrivere un algoritmo di costo O(n) per calcolare
tutti i valori dell'array B[1..n], senza effettuare divisioni e utilizzando spazio aggiuntivo O(1). (Questo
esercizio è stato proposto da Google durante i colloqui di assunzione)

La mia idea è quella di andare a fare il prodotto di ogni cella da destra a sinistra in maniera ricorsiva passandolo per parametro come "rightProduct". Quando arrivo al caso base, la ricorsione inizia a tornare "indietro" (è giusto? come uno "stack") dando come parametro rightProduct. Prima di fare il return però calcolo il leftProduct che è infatti il valore di ritorno dalla ricorsione ed è il prodotto delle celle di sinistra prima della cella "s". In sostanza basta vedere il codice come l'ho scritto (s è l'indice dell'array b la cui cella viene calcolata). b è il prodotto tra leftProd e rightProd:

public static int product(int a[], int b[], int s, int right)
{
	if(s==-1)
		return 1;
	int rightProd=1;
	if(s<n-1)
		rightProd = a[s+1]*right;
	int leftProd = product(a,b,s-1,rightProd);
	if(0<s)
		leftProd *= a[s-1];
	b[s]=leftProd*rightProd;
	return leftProd;
}

Ho un altro dubbio, che prestazioni temporali ha questo algoritmo? $\theta(n)$ o meglio $\theta(2n)\cong \theta(n)$ ?
Prestazioni di spazio $\theta(1)$ credo perché uso 3 variabili. (vale anche se è una ricorsione?)

[vict85]

Perché usare un algoritmo ricorsivo? Puoi implementare la stessa cosa con due semplici cicli for.

[absinth]

Ma come faccio? Non posso fare divisioni... tra l'altro in uno spazio $O(1)$. Non riesco a immaginarmi la tua soluzione

[apatriarca]

Puoi usare la seguente idea:
\[B_i = \frac{\prod_{j=0}^{n-1} A_j}{A_i} = \prod_{j=0}^{i-1} A_j\;\prod_{j=i+1}^{n-1} A_j \]
A questo punto fai due iterazioni. Nella prima fai il prodotto di tutti i valori precedenti al valore corrente e nel secondo fai il prodotto di tutti quelli successivi.

[absinth]

si è la stessa cosa che ho fatto nella ricorsione però facendo con dei semplici cicli come dice vict85 devo farlo per ogni $B_i$ quindi $n$ volte con prestazioni temporali complessive $O(n^2)$.
Anche se supponiamo di non calcolare ogni volta il primo prodotto perché ce lo passiamo da un ciclo all'altro, il secondo ci tocca calcolarlo perché decresce per ogni $i$ e non possiamo dividere. Quindi anche solo calcolando il secondo abbiamo
$O(n-2 + n-3 + ... +1) \cong O(n^2)$

[apatriarca]

No. Per calcolare il secondo pezzo è sufficiente partire dalla fine e memorizzare il valore finora calcolato. Sono semplicemente due passaggi sullo stesso array..

[vict85]

Ogni funzione ricorsiva può essere tradotta in modo iterativo senza aumentare l'uso della memoria (ovviamente deve mettere nel conto la memoria allocata nello stack per la chiamata ricorsiva). In questo caso comunque non servono strutture dati strane o cicli difficili da scrivere.

Detto questo i due due cicli usano solo due/tre variabili aggiuntive.

[absinth]

Ahhh che stupido non mi sono accorto che l'array B lo posso usare due volte per salvarci separatamente i prodotti
durante i due cicli.
Quindi era semplice l'esercizio
Grazie a voi per avermelo fatto notare. Soluzione con i cicli:

public static void product(int a[], int b[])
{
	private int prod=1;
	for(int i=0; i<n; i++)
	{
		if(i>0)
			prod*=a[i-1];
		b[i]=prod;
	}
	prod=1;
	for(int i=n-1; i>=0; i--)
	{
		if(i<n-1)
			prod*=a[i+1];
		b[i]*=prod;
	}
}