Thread: Is there anyway to optimise this recursive algorithm so I don't get an OutOfMemory error?

My overall project is to create a tree and use Huffman coding to encode and decode a given file. I am at the point where I need to decode my file. To do this, i am having to step through my Huffman Tree until I reach a bottom most leaf and then return the Byte represented by that leaf. I traverse the tree according to the bit string given to the method. AKA if the current bit is 1, I go to childOne in the tree and so forth. The problem is that I keep getting an outOfMemory error. Is there any way to optimize this code so that it won't use as much memory?

public static int decode(List<Integer> bitArray, HuffmanNode root, int startingPosition,
                          ArrayList<Byte> finalArray)
    {
    HuffmanNode childOne;
    HuffmanNode childZero;
    int currentBit = bitArray.get(startPosition);
    byte newByte;
 
            childOne = root.getChildOne();
            childZero = root.getChildZero();
            if(childOne == null && childZero == null)
            {
               finalArray.add(root.getByteRepresented()); 
               return startPosition;
            } 
            else if(currentBit == 1)
            {
                startPosition++;
                startPosition = decode(bitArray,childOne,startPosition,finalArray);
            }
            else
            {
                startPosition++;
                startPosition = decode(bitArray,childZero,startPosition,finalArray);
            }
 
         return startPosition;
 
}

I am needing to know the place in the bitArray that it ended as well as put the specified Byte into an array, so that is why I am putting the Byte into the array within the method and returning and int. Basically, is there any better way to get this done?

Your "out of memory" error is likely caused by an infinite recursion condition. Check that the base case actually exists so that the recursive algorithm has an exit.