Recursion - why use return statement

Question

I am learning recursion and below is one example that I am tracing through to better understand it

public static void main(String []args) {
    new TestRecursion().strRecur("abc");
}

public void strRecur(String s) {
    if(s.length() < 6) {
        System.out.println(s);
        strRecur(s+"*");
    }
}

Below is what I have understood so far. - In the first call to strRecur("abc"), the method gets added to execution stack. It prints "abc" before pausing due to a recursive call with parameter "abc*".

The second call with "abc*", pushes method strRecur(abc*) to the stack and prints "abc*" to console.
The third call with "abc**", pushes method strRecur(abc**) to the stack and prints "abc**" to console.
The fourth call with "abc***", pushes method strRecur(abc***) to the stack. Since the base condition is met, the method completes (without printing anything) and pops out of the stack.
The third call with "abc**" is completed and popped out. Since there is no pending code to execute nothing happens.
The second call with "abc*" is completed and popped out. Since there is no pending code to execute nothing happens.
The initial call with "abc" is completed and popped out. Since there is no pending code to execute nothing happens.

Prints following to the console -

abc
abc*
abc**

I think I understand what is happening here. Now, I want to try a slight variation of this code. Instead of callingstrRecur(s+"*"), I would like to do return strRecur(s+"*")

public class TestRecursion {

    public static void main(String []args) {
        new TestRecursion().strRecur("abc");
    }

    public String strRecur(String s) {
        if(s.length() < 6) {
            System.out.println(s);
            return strRecur(s+"*");
        }
        return "Outside If";
    }
}

My expectation was that, once strRecur(abc***) pops out, it's output (abc***) would be returned to the next strRecur() on the stack, so I would see abc**** printed in the console. Same for other recursive calls as well.

However, the output in this case is exactly the same as when there is no return statement. My understanding (which of course is not correct) stems from the recursive factorial implementation, where we do something like

return n * fact(n-1);

Here fact(n-1) is resolved with the returned value of n, once the previous method on the stack completes. Why doesn't return behave in the same way in this example?

Just a quick word of advice: I found that when trying to understand recursion it helps if you print out the details of every call. For example start your recursive method with something like System.err.println( "> strRecur s="+s); and before returning, you do System.err.println("< strRecur s="+s);. Then you can trace what is being called with what input parameter and in what order. Maybe not with this relatively simple recursion, but when you get to learn about more complicated scenarios, this may help a lot. — biziclop
– biziclop, Commented Jul 13, 2017 at 9:54

Eran · Accepted Answer · 2017-07-13 09:49:38Z

9

The output of both methods is produced by the println statements within the recursive method, which is why it is identical in both methods.

The value returned by the second method is not printed anywhere, which is why you don't see it displayed.

If you would print the result of the second method, you will see it is "Outside If", since that's the output of the last recursive call, which is then returned by all the other method calls.

If you want the output to be abc***, you should

return s;

instead of

return "Outside If";

The full code would be:

public static void main(String[] args) {
    System.out.println(new TestRecursion().strRecur("abc"));
}

public String strRecur(String s) {
    if(s.length() < 6) {
        return strRecur(s+"*");
    }
    return s;
}

edited Jul 13, 2017 at 9:49

answered Jul 13, 2017 at 9:41

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Michael Over a year ago

Additionally, and I don't know what OP's requirements are, you may need to change the 6 to 5. His first example only gets as far as abc**

Sylwester · Accepted Answer · 2017-07-13 17:39:24Z

0

Here is how to make it return the value instead of printing it:

public static void main(String[] args) {
    String result = StrRecur("abc");
    System.out.print(result);
}

public static String StrRecur(String s) {
    if(s.length() < 6) {
        return s + "\n" + StrRecur(s+"*");
    }
    return "";
}

This does the same, but the side effect happens only in main.

answered Jul 13, 2017 at 17:39

Sylwester

48.9k4 gold badges52 silver badges83 bronze badges

Collectives™ on Stack Overflow

Recursion - why use return statement

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related