Double recursion in one method

Question

I can't visualize the way the program is executed because of the second recursive call. What's the easiest way to go about solving this?

public class Recursion 
{

public static void main(String[] args) 
{
    f(3);

}

public static void f(int x)
{
    if(x>0)
    {
        System.out.println(x + "top");
        f(x-1);
        System.out.println(x + "bottom");
        f(x-1);
    }
    System.out.println("bert");
}
}

What do you want? Remove the second recursion call or understand what it does? — Michael Butscher, Dec 17 '18 at 01:21
understand how to traverse through the f method with both recursions — Slicknature, Dec 17 '18 at 01:24
I already know the output I just want to understand how the recursion works. I can usually do a problem with one recursive call but this one has two recursive calls. I want to know how would someone would traverse through the method to get the output. — Slicknature, Dec 17 '18 at 01:27
you can visit [this question and answer](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) to have a clearer look at how recursive work. — Dang Nguyen, Dec 17 '18 at 01:31
@Dang Nguyen That topic discusses one recursive call only. This one has two. — Slicknature, Dec 17 '18 at 01:34
*I can't visualize the way the program is executed because of the second recursive call. What's the easiest way to go about solving this?* **Debugger**. — Elliott Frisch, Dec 17 '18 at 01:42
Elliott is right. Use your debugger and look at the entire call stack at each step, not just the top frame. This is by far the best way to understand what's going on. — Dawood ibn Kareem, Dec 17 '18 at 01:44
@Slicknature I think the confusion is stemming from thinking of it as "the same function" being called many times. If you think of it as "many copies of the same function being called", then it may be clearer: (copy from the Q&A I sent you). And one or two or multiple call is the same. — Dang Nguyen, Dec 17 '18 at 01:45
Possible duplicate of [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — Dang Nguyen, Dec 17 '18 at 01:47

Jason · Answer 1 · 2018-12-17T03:23:31.380

In the end, the following tree would have been built:

      \
      /\
     /  \
    /\  /\
   /\/\/\/\

Think of each branching point as a call to f() with a particular value (3 is the first branch point, 2 for the next one down, then 1, then 0).

Step by step:

The first call f(3) is the line at the top.

The next call is f(2):

      \
      /
     /

The next call is f(1):

The next call is f(0):

Then control returns up one layer and the next call is f(0) again:

And so on:

      \
      /
     /
    /\
   /\

      \
      /
     /
    /\
   /\/

      \
      /
     /
    /\
   /\/\

And then the pattern repeats for the other side.

score 1 · Answer 2 · answered Dec 17 '18 at 01:46

It performs much the way a single recursion method does. Let's break this down:

if(x>0) //x == 3
{
    System.out.println(x + "top");
    f(x-1);  //Passes in 2
    //---------- Break 1
    System.out.println(x + "bottom");
    f(x-1);
}

It hits the recursive call and goes to:

if(x>0)  //x == 2
{
    System.out.println(x + "top");
    f(x-1); //passes in 1
    //------- Break 2
    System.out.println(x + "bottom");
    f(x-1);
}

And again:

if(x>0) //x == 1
{
    System.out.println(x + "top");
    f(x-1);  //Passes in 0
    //----------- Break 3
    System.out.println(x + "bottom");
    f(x-1);
}

Then in the next recursive call the base case is hit so it does not enter the if and prints bert and then exits the method.

Then the recursive call goes back to caller, which is is at break 3:

if(x>0) //x == 1
{
    System.out.println(x + "top");
    f(x-1);  //Passes in 0
    //----------- Break 3
    System.out.println(x + "bottom");
    f(x-1);
    //---------- Break 4
}

So it then hits the second recursive call and passes in 0. This will hit the base case and stop the recursion.

Then the method will return to the caller, which is at break 4. This ends that method, so it returns to the caller of that method, which is break 2.

if(x>0)  //x == 2
{
    System.out.println(x + "top");
    f(x-1); //passes in 1
    //------- Break 2
    System.out.println(x + "bottom");
    f(x-1);
}

Then the second recursive call will be hit and pass in x == 1, which is the same case as above, so I won't repeat it. Then this returns to the method that called it, which is break 1. Then that method calls the second recursive call, which is x == 2, which again is a repeat.

score 0 · Answer 3 · answered Dec 17 '18 at 01:48

To visualize the call graph of this code, you need to draw a tree. Each of its inner nodes has exactly 2 children.

Another way to visualize the call graph is to add a string parameter called indentation to the method. Each output line would be indented, and on each recursive call the indentation would get a little longer.

public static void f(String indentation, int x) {
    if (x > 0) {
        System.out.println(indentation + "first");
        f(indentation + "....", x - 1);
        …
    }
}

Rax · Answer 4 · 2018-12-17T06:35:12.463

0

This program is executed as per the way you have written the logic. There could be two things:

You are not able to visualize the output. If this the case, try to visualize the method calls in terms of stack frame, put them one over the other as per the sequence of the calls. This way if you dry run your program, you will come up with the same output. I just did that. In case you want I can attach the screenshot.
If your concern is not as explained above, please help us understand the problem statement a little better.

edited Dec 17 '18 at 06:35

answered Dec 17 '18 at 02:03

Rax

323
1
5
17

Added the screenshot of the program execution. This is the output even I am getting. Hope this helps. – Rax Dec 17 '18 at 04:44

Double recursion in one method

4 Answers4