è un giusto prg ricorsivo?

[Lucked]

Vi posto in versione provabile un programma ricorsivo che ho trovato su un sito, secondo voi è una giusta ricorsione? Ho messo 2 System.out.println commentati, se le decommentate vedete i numeri di confronti che fa, e i numeri prossimi che si confrontano..si fa cosi??

class Ricorsione{
  public static void main(String[] args){

  int[] a = {90,50,6,9,5,2,80,90,6,7,5,4};


    System.out.println( minRic(a,0,a.length-1) );
  }



  public static int minRic(int a [ ], int from, int to)
  {
      if (from == to)
              return a[from];
      int mid = (from + to)/2;
      // cerchiamo ricorsivamente il minimo
      // nella prima e nella seconda metà dell'array:


      int min1 = minRic(a, from, mid);
      //System.out.println(min1);
      int min2 = minRic(a, mid+1, to);
      //System.out.println(min1);
      if (min1 <= min2)
              return min1;
      else
              return min2;
  }


}

p.s: deve trovare il minimo...allora tanto vale che lo scorre tutto l'array per fare cosi o sbaglio?

[anx721]

Il programma ricorsivo è giusto: se l'array ha un solo elemento ritorna quell'elemento come il minimo (caso base); se no spezzetta il prblema originario nei due sottoproblemi di calcolare il minimo nel sottoarray sinistro e nel sottoarry destro, richiamando ricorsivamente il metodo sui due sottoarray, e quindi ritorna il piu piccolo fra i due minimi trovati. Ovviamente una semplice ricerca lineare nella'rrya sarebbe pure piu efficente, l'algoritmo ha solo lo scopo di mostrare l'uso della ricorsione.

[Lucked]

non mi sembra vero che spezzetta il problema :bubu: non mi convince la clausola "if (from == to)": fa fare tanti cicli per cosa? all'inizio vale (0+11)/2 = 5 e poi 5/2 = 2 e poi 2/2 = 1 ma ancora non va bene.... 1/2 = 0 allora coincide e restituisce il primo elemento?? invece secondo me, doveva modificare i 2 indici e avvicinarsi al valore 2

[Lucked]

tant'è mi pare che se davvero dividesse l'array dovrebbe fare meno confronti ed essere piu veloce di un algoritmo lineare

[anx721]

Quello che tu indichi e che si conclude restiruiendo il primo elemento è solo uno dei rami delle chiamate ricorsive...

              {90,50,6,9,5,2, 80,90,6,7,5,4}2
                 /                     \
            {90 50 6 9 5 2}2       {80 90 6 7 5 4}4
              /       \            /          \
      {90 50 6}6    {9 5 2}2      {80 90 6}6  {7 5 4}4
         / \        /    \         /    \      /     \
   {90 50}50{6}6  {9 5}5 {2}2  {80 90}80{6}6  {7 5}5 {4}4
     /  \          /\             / \           / \
  {90}90{50}50  {9}9{5}5       {80}80{90}90  {7}7 {5}5

[Lucked]

Si credo di avere capito. Alla fine confronta sempre e solo 2 numeri, vero? Quindi è piu veloce di un algoritmo lineare immagino

[anx721]

Non confronta solo due elementi, perche nel fare tutte le chiamate ricorsive alla fine fa sempre n confronti, come una ricerca lineare; per di più c'è una maggiore inefficenza dovuta al fatto di metter su tutte le chiamate ricorsive, che vengono accumulate in uno stack e restano tutte in memoria finche non si arriva al livello piu basso di ricorsione.

Un altro algoritmo riorsivo per fare la stessa cosa è il segunete:

public static int minRic(int a [ ], int from, int to){
      if(from == to)
          retrun a[from]
      min = minRic(a, from + 1, to);
      if(min < a[from])
          retrun min;
      else
          retrun a[min]
} 

In questo caso il problema originario non è suddiviso in 2 sottoproblemi cosituiti dal sottoarray sinistro e dal sottoarry destro, in vece si crea un unico sotto problema costituito dal sottoarry che va dal prossimo indice (form + 1), fino alla fine.

In generale la ricorsione la si usa non per aumentare l'efficenza, ma per la facilità con cui si puo scrivere un algoritmo, come si vede nel caso di algoritmi sugli alberi; per rendertene conto puoi provare a calcolarti l'altezza di un albero in modo non ricorsivo...

[ladyBlu]

il linguaggio nel titolo