Rekursion vs. Iteration

[negaH]

Code:

  function XorVectorBits(Bits: std_logic_vector, Index: integer) return std_logic;
  variable 
    Result: std_logic;
  begin
    Result := Bits(Index);
    if Index < Bits'High then
      Result := Result xor XorVetorBits(Bits, Index +1);
    end if;
    return Result;
  end function; 

  function XorVextorBits(Bits: std_logic_vector) return std_logic;
  variable 
    Result: std_logic;
    Index: Intger;
  begin
    Result := '0';
    for Index in Bits'Range loop
      Result := Result xor Bits(Index);
    end loop;    
    return Result;
  end function;

Oben sieht man zwei Funktionen in VHDL, erstere ist rekusiv die zweite nutzt eine Schleife. Beide beschreiben ein Verhalten einer späteren Hardware.

Das Signal Bits stellt man sich zb. wie ein Datenbus vor der aus zb. 16 Datenleitungen besteht. Die Boolsche Funktion lautet in Worten: Verknüpfe alle Datenleitungen in Bits per XOR und gebe das Resultat, ein Bit, zurück.

Beides wird bei der Synthese in Hardware exakt identische Resultate erzeugen. Nämlich ein XOR Gatter mit Bits'Range Inputs und einem Output.

Ok, es dürfte klar sein das das ein sehr enfaches Beispiel ist und hier der Vorteil in der formalen Schreibweise einer Rekursion noch nicht zum tragen kommt.

Gruß Hagen

[idefix2]

Ich muss zugeben, dass mich das verblüfft. Ich hätte nicht geglaubt, dass es im wirklichen Leben tatsächlich Systeme gibt, die derartige rekurive Strukturen als Eingabe hernehmen und die Rekursion in parallel arbeitende Harware auflösen.

[negaH]

Denke mal drüber nach warum ich in diesem Thread immer wieder betone das das nur eine Form einer Schreibweise ist und eben nicht direkt im Zusammenhang mit irgendwas Realem, wie eben Hardware, steht.

Rekursiv vs. Iterativ ist eine Frage der Schreibweise eines Algorithmus. Es ist nicht der Algorithmus selber noch dessen praktische Realisierung in Hardware.

Man muß immer strikt abstrahieren und eine Frage, je nach gewünschter Sichtweise, beantworten.

Bei "Rekursv vs. Iterativ" gilt erstmal das es da keinen Unterschied geben kann in der Performance und Speicherverbrauch. Erst wenn man die benutzte Hardware oder Softwaretools berücksichtig ändert sich die Antwort, bzw. erst dann macht es Sinn den Speicherverbrauch/Performance als Entscheidungskriterium heran zu ziehen. Aber..., dann bewertet man nicht mehr "Rekursiv vs. Iterartiv" sondern defakto die Fähigkeiten der btrachteten Softwaretools und Hardware, wie sie die unterschiedlichen Schreibweisen eines Algorithmus umzusetzen in der Lage sind.

Wer also behauptet: Rekursiv sei oft langsammer als Iterativ in der Performance oder eben mehr Speicher verbraucht auf Grund eines notwendigen Stackframes, der bewertet einen ASIC als Hardware, und eben nicht mehr objektiv zwei Schreibweisen eines Algos.

Gruß Hagen