Stack overflow bei einer endrekursiven Funktion (Anwendung: Spezialform des Package Merge)

[LemE.Tweakit]

Hallo zusammen,

ich habe ein Problem mit einer rekursiven Methode. Die Anwendung ist eine Huffman Codierung mit einer Spezialform des Package Merge (nach Turpin und Moffat).
Der stack overflow kommt dadurch zustande, dass ich einen beliebig tief geschachtelten Baum von "Packages" habe, den ich, von der Wurzel aus, rekursiv durchgehen muss um die Auftrittshäufigkeit einzelner Werte zu zählen.

Mir ist klar, dass Iteration in Java immer der Rekursion vorzuziehen ist, aber für diese spezielle Struktur kann ich keine vollständig iterative Lösung bauen, weil die Bäume beliebig tief verschachtelt sein können. Oder habe ich hier etwas übersehen??

Eine Reduktion der Iterationstiefe habe ich bereits versucht, jedoch hat das auch nicht viel bewirkt und ich möchte eine wasserdichte Lösung bzw brauche sie... Dementsprechend ist auch eine simple vergrößerung des Stack nicht sinnvoll, weil ich ggf sehr große Datenmengen codieren muss...

Nachfolgend die Struktur des Package Objekts...

import java.util.*;

public class Package implements Comparable<Package>{

	int freq;
	int sign;
	Package[]children;
	static int amount=0;
	/** Erzeugt einen Package Knoten ohne Kinder
	 * 
	 */
	public Package(){
		
		int freq=0;
		int sign=0;
		children=new Package[0];
	}
	/** Erzeugt einen Package Knoten mit einem Kind
	 * 
	 * @param child
	 */
	public Package(Package child){
		
		int freq=child.freq;
		int sign=0;
		children=new Package[1];
		children[0]=child;
	}
	/**Erzeugt einen Package Knoten mit mehreren Kindern (Package Array)
	 * 
	 * @param children
	 */
	public Package(Package []children){
		
		int freq=0;
		int sign=0;
		this.setChildren(children);
	}
	/**Erzeugt einen Package Blatt - children[]=null
	 * 
	 * @param freq
	 * @param sign
	 */
	public Package(int freq, int sign){
		
		this.freq=freq;
		this.sign=sign;
		children=new Package[0];
	}
// Es folgen getter und Setter usw....

Der Stackoverflow passiert dann in der folgenden Methode...

public void amountSign(int sign){
		if(this.children.length==0){
			if(this.sign==sign)
				amount++;
		}else
		{
			for(int i=0;i<this.children.length;i++){
				this.children[i].amountSign(sign);
				
			}
		}
}

Ich bin wirklich für jeden Ansatz dankbar...

 

[Mr.Byte]

Ich habe mal gehört, dass man wirklich jede Rekursion auch Iterativ abarbeiten kann.

 

[Flown]

So ich kann dir sagen, dass es leicht möglich ist, dass in eine Schleife zu verwandeln. Hab dir mal ein analoges Bsp geschrieben für Blätter zählen (BFS Strategie).

import java.util.LinkedList;
import java.util.Queue;

public class Test {
  public static void main(String... args) {
    Node parent = new Node(1, new Node(2, new Node[] { new Node(3, new Node[] { new Node(4), new Node(5) }), new Node(6) }));
    
    int leafs = 0;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(parent);
    while (!queue.isEmpty()) {
      Node cur = queue.poll();
      if (cur.children.length == 0) {
        leafs++;
      } else {
        for (Node c : cur.children) {
          queue.offer(c);
        }
      }
    }
    System.out.println(leafs);
  }
  
  static class Node {
    public Node[] children = null;
    public Integer data = null;
    
    public Node(Integer data, Node... children) {
      this.data = data;
      this.children = children;
    }
  }
}

 

[LemE.Tweakit]

Richtig Mr.Byte, das haben mir meine Professoren auch eingetrichtert, jedoch ist die Iterative Lösung für mein Empfinden 1. nicht immer so leicht zu finden und 2. nicht so elegant aber dafür meist wesentlich schneller...

 

[LemE.Tweakit]

... und ein dickes Dankeschön an Flown, ich werde mich gleich mal hinsetzen und dein Beispiel nachvollziehen...