[C] Valori restituiti da una funzione ricorsiva

[toni00c]

ciao
sto facendo pratica sulla ricorsione , un argomento che proprio non mi va giù

avendo scritto un algoritmo iterativo

=========
int main ()
{
  int a ; /* base */
  int n ; /* limite */
  int i ; /* contatore */
  int j ; /*  contatore */
  int sommatoria = 0 ;
  int potenza  ;

  printf (" inserisci la base \n \n" ) ;
  scanf ("%d" , &a ) ;

  printf (" inserisci il limite \n \n" ) ;
  scanf  ("%d" , &n ) ;


  for ( i = 0 ; i <= n ; i++ )
  {
	
	  
	  for ( j = 0 ; j < 1 ; j++ )
  {
	  if ( i == 0 )
		  potenza = 1 ;

	  else
	  potenza *= a ;
	  
	  
  }

	  sommatoria  += potenza  ;

  }


  printf ("potenza is %d \n \n " , potenza ) ;
  printf (" la sommatoria e %d \n\n" , sommatoria ) ;

=======================

ne ho scritto un equivalente ricorsivo con qualche dubbio

int ricSomma ( int n , int lim)

{
	if ( lim == 0 )
		return 1 ;

	else
		return 1+ n * ricSomma ( n , lim - 1 )   ;

}

nella chiamata ricorsiva della funzione ricSomma ho specificato casualmente "+ 1 "
ora la mia domanda è :
che cosa restituisce la funzione a ogni chiamata ricorsiva ?
qual'è la sequenza di attivazione nello stack?

ad es il fattoriale di 5! calcolato in modo ricorsivo restituirebbe

5 * 4!
4 * 3!
3 * 2!
2 * 1!
1


1*2
3*2
4*6
5*24
= 120


nel caso della mia funzione però c'è un pezzo che mi manca alla comprensione!
mi potreste aiutare ?
grazie

[lolide]

Ma devi fare il calcolo delle potenze oppure il calcolo del fattoriale ?

[toni00c]

no devo fare il calcolo di una sommatoria di A^I


che va da
indice I

a
indice N


sto cercando che cosa restituisce la chiamata ricorsiva di "ricSomma"

[_Alfabetagamma_]

Quello che hai scritto tu rende

1+n*(1+n*(1+n*(1+n* ecc ecc

Tu volevi fare a^i?

un modo potrebbe essere

int ricSomma ( int num , int exp )

{
	if ( exp == 0 ) return 1 ;

	else	return num*ricSomma ( num, exp - 1 );

}

[toni00c]

Originariamente inviato da _Alfabetagamma_
Quello che hai scritto tu rende

1+n*(1+n*(1+n*(1+n* ecc ecc

Tu volevi fare a^i?

un modo potrebbe essere

int ricSomma ( int num , int exp )

{
	if ( exp == 0 ) return 1 ;

	else	return num*ricSomma ( num, exp - 1 );

}

ciao io devo fare il calcolo di una sommatoria , mentre nel tuo codice hai calcolato una potenza
ragioniamo un po , la ricorsione è sempre brigosa

grazie

[ramy89]

Cerco di spiegartelo nel modo più facile possibile.
La funzione ricorsiva deve essere una sorta di cipolla.Devi essere sicuro che prima o poi l' argomento debba diventare un determinato numero.
Per esempio:

int power(int base,int exp)
{
    if(exp==1)
        return base;
    else 
        return base*(base,exp-1);
}

Questa è la classica funzione ricorsiva,per fartela rendere più facile,inizia a calcolarla al contrario,dal cuore della cipolla.
exp può essere un qualsiasi numero,ma alla fine diventerà per forza 1.
Quindi il ritorno è:

1*power(base,1+1)*power(base,base,2+1)*....*power(base,n);

Attenzione poi che se gli passi un esponente negativo va avanti all' infinito perchè l' esponente non arriva mai a 1.

Prendiamo poi il tuo caso:

int ricSomma ( int n , int lim)

{
	if ( lim == 0 )
		return 1 ;

	else
		return 1+ n * ricSomma ( n , lim - 1 )   ;

}

Se fossi un computer (e sarei lentissimo a fare le cose ) ti dico come farei,ecco un esempio di chiamata:

ricSomma(3,3);

La eseguo su un pezzo di carta,siccome lim è 3,per ora scrivo 1+3*ricSomma(3,2).
Poi faccio :

ricSomma(3,2);

lim è ancora diverso da 0,per cui al risultato aggiungo 1+3*ricSomma(3,1).
Stavolta lim è uguale a 1,infatti il principio della funzione ricorsiva è che prima o poi ritornerà un valore fisso,per cui aggiungo come risultato 1.
Adesso so che ricSomma(3,3)=1+3*ricSomma(3,2);
ricSomma(3,2)=1+3*ricSomma(3,1);
ricSomma(1,1)=1.
Allora sostituisco:

result=1+3*(1+3*(1+3*(1)));

Il cuore della cipolla è sempre uno,parto da la a fare i conti.
Il risultato viene 40,ma ci si mette sempre troppo tempo.
Per fare l' algoritmo devi sapere il caso generale,in questo caso non viene proprio una somma ricorsiva.
Fai finta che sei tu che devi fare i conti,per fare 1+2 se non sai quanto è 2 fai 1+(1+1) e così via.
Ad esempio per la somma ricorsiva fai 2+(2-1),col presupposto che quando arrivi a 1 ti fermi.

[_Alfabetagamma_]

Ritengo non sia possibile fare una sommatoria di potenze volendo calcolare nella stessa funzione somma e esponente in modo ricorsivo. Potresti scrivere i valori di a^i in un array e sommarli ricorsivamente, o trovare a^i ricorsivamente. Entrambi non credo sia possibile e se lo fosse non certamente in maniera facile.

[toni00c]

ciao ti ringrazio molto per la spiegazione , gentilissimo!
meglio del mio libro di testo

sei studente?

[ramy89]

Si, studio al primo anno di informatica.
Alla fine il trucchetto è provare a ragionare come se il computer sei te,io faccio sempre così.
Ciao