Recursive method returning a string at each step?

Question

I have a slight algorithmic problem. I think I miss something but can't exactly figure out what.

I want to walk to a tree containing strings and get out with a unique string.

Here is a graphical example of a tree I would like to parse.

My trees would have three different types of elements :

• Boolean operators (OR, NOT, AND) => BE
• other operators (like the =) => QO
• leaves (last elements) =>LEAF

I would like to end up with something like this :

"LEAF QO LEAF BE LEAF QO LEAF "

For now, I use a recursive method: I check the current element of the tree, and re run the method on its children depending on the type of elements I have. For each step I would populate my final string.

public class SingleTest { static String[] booleanElements = {"or", "and", "not"};

public static void main(String[] args) throws Exception {
    CommonTree tree = (CommonTree)parser.parse().getTree();

    if(true){
        String where = "";
        printWhere(tree, where);
        System.out.println(where);
    }       

}   

/*
 * Print to where tests
 */
public static boolean isBooleanElement(CommonTree t){
    return Arrays.asList(booleanElements).contains(t.toString().toLowerCase());
}


public static String printWhere(CommonTree t, String where){
    //---------------------
    // Checking node type
    //---------------------

    // Boolean Element 
    if (isBooleanElement(t)){
        // Continue parsing the tree                
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            printWhere((CommonTree)t.getChild(i), where+ "BE");
        }               
    }

    // Last element of tree (LEAF)
    else if(t.getChildCount() == 0 ){
        where = where + "LEAF";
    }

    // query operator
    else{
        // Continue parsing the tree    
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            printWhere((CommonTree)t.getChild(i), where + "QO");
        }                   
    }

    //---------------------
    return where;
}

My problem is that this code :

        String where = "";
        System.out.println(printWhere(tree, where));

returns "" (Which is logical due to my implementation).

So my question is, how can I get to have a non void string as final output ?

Hope this is clear enough Thank you for your help

Please note that this class is used for test purpose only, and I know that putting static everywhere is bad practice :)

EDIT :

The problem was (as expected) due to my lack of experience with recursion. Here is my final code :

public static String printWhere(CommonTree t, String where){
    //---------------------
    // Checking node type
    //---------------------

    // Boolean Element 
    if (isBooleanElement(t)){
        // Continue parsing the tree                
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            where = printWhere((CommonTree)t.getChild(i), where) + "BE";
        }               
    }

    // Last element of tree (LEAF)
    else if(t.getChildCount() == 0 ){
        where = where + "LEAF";
    }

    // query operator
    else{
        // Continue parsing the tree    
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            where = printWhere((CommonTree)t.getChild(i), where ) + "QO";
        }                   
    }

    //---------------------
    return where;
}

Answer 1

The problem is that you method printWhere does not return anything! You're appending the value to new where string, but since Java passes parameters by value, this newly created string is thrown away when you leave the method.

Make this method return string and return where at the end of it. Then, concatenate the result of a recursive call with the string from the above level. That's how recursion works.