rekursive Funktion

[Snucky]

Hallo,

in einem meiner Scripte soll in zufälliger Reihenfolge Werte einmalig aus einem Array gelesen werden. Ich speichere die genutzten keys in einem weiteren Array ab und gewährleiste mit einer Abfrage bei einem weiteren Funktionsaufruf, dass benutzte keys nicht doppelt verwendet werden, sondern ein neuer Aufruf des Zufallsalrogorhythmusses erofolgt. Letzteres geschieht per Rekursion. Nur funktioniert das Konzept in der Realität nicht:

var keys_used=new Array();
//0 ist immer minimum für den Rückgabewert
function errechne_zufall(maximum) {
 var ausschlag=Math.random();
 var rueck=Math.round(maximum*ausschlag);
 if (in_arr(rueck,keys_used)) {
  errechne_zufall(maximum);
 }
 else {
  keys_used.push(rueck);
  return rueck;
 }
}
function in_arr(needle,array) {
 var found=false;
 suche:for (var i=0; i<array.length; i++)
  if (array[i]==needle) {
   found=true;
   break suche;
  }
 return found;
}

Die einfache Frage ist, was mit der Rekursion nicht stimmt. Ich weiß es nicht.

Vielen Dank,
Snucky.

[Hans]

Hi Snucky !

var keys_used=new Array();
//0 ist immer minimum für den Rückgabewert
function errechne_zufall(maximum) {
var ausschlag=Math.random();
var rueck=Math.round(maximum*ausschlag);
if (in_arr(rueck,keys_used)) {
  errechne_zufall(maximum);
}
else {
  keys_used.push(rueck);
  return rueck;
}
}
function in_arr(needle,array) {
var found=false;
suche:for (var i=0; i<array.length; i++)
  if (array[i]==needle) {
   found=true;
   break suche;
  }
return found;
}

Also, so vom Gefühl her, würde ich sagen:

Beim ersten Aufruf ist das keys_used-Array leer. Die in_arr-Funktion liefert demzufolge "false" zurueck. Also wird die Zufallszahl in das Array aufgenommen und die errechne_zufall-Funktion verlassen.

Gruß

Hans

[lina-]

moin Snucky :)

Nur funktioniert das Konzept in der Realität nicht:

Richtig. Das liegt wahrscheinlich am return (bzw. am fehlenden return am Ende der Funktion). Ich bin didaktisch leider nicht so fit, dir zu erklären was Rekursion tut und vor allem was das auf Rückgabewerte für Auswirkungen hat - aber mir hat es immer sehr geholfen, wenn ich mir die Funktionen "aufgemalt" habe. Will heissen ich habe mir eine Zeichnung gemacht in der ich für ein paar Anwendungsfälle die zu erwartenden Variablen und Rückgaben aufschrieb und das dann mit dem tatsächlichen Programmablauf verglichen habe.

Aber wieso nutzt du überhaupt Rekursion?
Das Problem läßt sich doch in einer while-Schleife wunderbar lösen:

  
function errechne_zufall(maximum) {  
  var ausschlag=Math.random();  
  var rueck=Math.round(maximum*ausschlag);  
  while (in_arr(rueck,keys_used)) {  
   ausschlag=Math.random();  
   rueck=Math.round(maximum*ausschlag);  
  }  
  keys_used.push(rueck);  
  return rueck;  
 }  

PS: keine 100%ige Garantie dass das funktioniert... nicht getestet!

liebe Grüße aus Berlin
lina-

[Snucky]

Das Problem läßt sich doch in einer while-Schleife wunderbar lösen

Na, das sollte doch klappen :-) Danke!

[Struppi]

Die einfache Frage ist, was mit der Rekursion nicht stimmt. Ich weiß es nicht.

Es gibt keine sinnvolle Abbruchbedingung. Aber wozu soll die Rekursion gut sein?
Die Funktion in_arr() ist auch seltsam, wozu das Label?

Struppi.

[Joachim]

Hi,

in einem meiner Scripte soll in zufälliger Reihenfolge Werte einmalig aus einem Array gelesen werden. Ich speichere die genutzten keys in einem weiteren Array ab und gewährleiste mit einer Abfrage bei einem weiteren Funktionsaufruf, dass benutzte keys nicht doppelt verwendet werden

Warum das? Sortiere den Array per Zufall und lies einfach ein Element nach dem anderen aus. Bist Du bei myArray.length angekommen setzt Du den Index auf 0 und sortierst erneut.

Gruesse, Joachim

[JürgenB]

Hallo Snucky,

hier meine Vermutung:

var keys_used=new Array();
//0 ist immer minimum für den Rückgabewert
function errechne_zufall(maximum) {
var ausschlag=Math.random();
var rueck=Math.round(maximum*ausschlag);

hier erhält rueck einen Wert ...

if (in_arr(rueck,keys_used)) {
  errechne_zufall(maximum); // <-----
}
else {
  keys_used.push(rueck);
  return rueck;
}
}

... der im Rekursionsfall nicht zurückgegeben wird.

Wenn du in der Zeile mit // <----- einfach
return errechne_zufall(maximum);
schreibst, sollte es gehen.

Allerdings schließe ich mich den anderen an: ich würde hier auch auf Rekursionen verzichten.

Gruß, Jürgen

[lina-]

moin JürgenB :)

... der im Rekursionsfall nicht zurückgegeben wird.

Wenn du in der Zeile mit // <----- einfach
return errechne_zufall(maximum);
schreibst, sollte es gehen.

ha! Ich wünschte ich könnte meine wirren Gedanken (die deinen Ausführungen absolut entsprochen haben) ebenso gut auf den Punkt bringen ;)

liebe Grüße aus Berlin
lina-