Resolving a stack with 2 recursive calls

Question

I'm trying to refresh my skills in recursion and so far everything has gone well. However, I have never seen a problem where a string is the value of two recursive calls. Does the first recursive call ignore the rest of the statement? Is the 2nd recursive call still taken into account when it is resolved? I tried tracing it under the assumption that like a return statement, the first recursive call would break the loop. Therefore, I was under the impression that the rest of the code in the if statement would not be taken into account.

public class Example {
    public static String encrypt(String word) {
        int pos = word.length() / 2;
        if (pos >= 1) 
            word = encrypt(word.substring(pos)) + encrypt(word.substring(0,pos));
        return word;
    }

    public static void main(String []args){
        System.out.println(encrypt("SECRET"));
     }
}

While my expected output was "TETRET", the actual output was supposed to be "TERCES." Anyone mind explaining where my tracing or logic went wrong?

You're overthinking it. Just because it's recursive doesn't mean it's any different to any other function. Barring some exception mechanic every instance will get called. The arguments of a function get resolved before the function is executed. — Tibrogargan
– Tibrogargan, Commented May 11, 2019 at 1:43

GBlodgett · Accepted Answer · 2019-05-11 01:28:31Z

1

I tried tracing it under the assumption that like a return statement, the first recursive call would break the loop.

This is incorrect. Both will be evaluated.

word = encrypt(word.substring(pos)) + encrypt(word.substring(0,pos));

The first recursive call will get pushed onto the stack, and the second will be saved on the stack to be evaluated once the first call has been returned to the call stack. Here's a visual representation:

This is assuming 3, 4, and 5 reach the base case and thus do not continue the recursion

answered May 11, 2019 at 1:28

GBlodgett

12.8k4 gold badges33 silver badges48 bronze badges

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

Comments

AGA · Accepted Answer · 2019-05-11 01:54:45Z

The word is returned in reverse order. I am unsure what you were trying to do instead. Here is a partial trace of your code, using "ABCDEF" instead of "SECRET", showing how it works :

+=================================+====================+===========================================+==============+==========================================+==============+
|       word (initial call)       | pos (initial call) |               word (call 2)               | pos (call 2) |              word (call 3)               | pos (call 3) |
+=================================+====================+===========================================+==============+==========================================+==============+
| "ABCDEF"                        |                  3 |                                           |              |                                          |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
| encrypt("DEF") + encrypt("ABC") |                    | "DEF"                                     |            1 |                                          |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    | encrypt("EF") + encrypt ("D")              |              | "EF"                                     |            1 |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    |                                           |              | encrypt("F") + encrypt("E")              |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    |                                           |              | (call 4 returns "F", call 5 returns "E") |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    |                                           |              | "FE"                                     |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    | (call 3 returns "FE", call 6 returns "D") |              |                                          |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+
|                                 |                    | "FED"                                     |              |                                          |              |
+---------------------------------+--------------------+-------------------------------------------+--------------+------------------------------------------+--------------+

Here is the order in which the calls are made and "resolved" (by resolved, I mean that the return statement of the function is executed) :

encrypt("ABCDEF")
encrypt("DEF")
encrypt("EF")
encrypt("F")
resolution of encrypt("F") // returns "F"
encrypt("E")
resolution of encrypt("E") // returns "E"
resolution of encrypt("EF") // returns "FE"
encrypt("D")
resolution of encrypt("D") // returns "D"
resolution of encrypt("DEF") // returns "FED"
encrypt("ABC")
(...)

Of course the same logic applies to encrypt "ABC" as it did to encrypt "DEF", so if you understand this part you should understand the rest.

WJS · Accepted Answer · 2019-05-11 02:04:08Z

0

If you place the print statement as I have shown, you can see how the returned word and pos are altered. Then just backtracking off the stack, the word is reconstructed in reverse order.

public class Example {
   public static String encrypt(String word) {

      int pos = word.length() / 2;
      System.out.println(word + " " + pos);
      if (pos >= 1) {
         word = encrypt(word.substring(pos)) + encrypt(word.substring(0, pos));
      }
      return word;
   }

   public static void main(String[] args) {
      System.out.println(encrypt("SECRET"));
   }
}

Produces the following output:

SECRET 3
RET 1
ET 1
T 0
E 0
R 0
SEC 1
EC 1
C 0
E 0
S 0
TERCES

edited May 11, 2019 at 2:04

answered May 11, 2019 at 1:44

WJS

40.2k4 gold badges27 silver badges46 bronze badges

Collectives™ on Stack Overflow

Resolving a stack with 2 recursive calls

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related