Java recursion output different from expected

Question

Just when I thought I was starting to understand recursion this one seems simple when n is 1 but when n is 2 In my head I end up with [[, [, [,]

public void ps (int n){

  if (n==0) {
    System.out.print ("*");  
  }
  else {
    System.out.print ("[");
    ps (n-1);
    System.out.print (",");
    ps (n-1);
    System.out.print ("]");
  }
}

well what do you think it should do and what does it do? Start with that. — twain249, Mar 22 '17 at 22:13
@Jason signature of your method should look like `public void ps(int number)` instead of `Public void ps (int n)`. — catch23, Mar 22 '17 at 22:20
Sorry was typing on my phone that type o was not in the program — Jason, Mar 22 '17 at 22:22
Edit your question. Make it clear. Tell what you want to achieve, what you expect to happen, and what happens instead. Use the preview, and don't post your question until it's perfectly clear. — JB Nizet, Mar 22 '17 at 22:29

twain249 · Accepted Answer · 2017-03-22T22:24:13.313

  ps(2):
     Current output ""
     n != 0 so else: print [ output = "[" 
     call ps(1)
     ps(1):
       Current output "["
       n != 0 so else: print [ output = "[[" 
       call ps(0)
       ps(0):
        Current output "[["
         n == 0: print "*" output = "[[*"
         return
     ps (1): after first call
       output = "[[*"
       print "," output = "[[*,"
       call ps(0):
       ps(0):
         current output "[[*,"
         n == 0: print "*" output = "[[*,*"
         return
    ps(1): after second call
       output = "[[*,*"
       print "]" output = "[[*,*]"
       return
  ps(2): after first call
    output = "[[*,*]"
    print , output = "[[*,*],"
    call ps(1)
             ps(1):
       Current output [[*,*],
       n != 0 so else: print [ output = "[[*,*],[" 
       call ps(0)
       ps(0):
        Current output "[[*,*],[" 
         n == 0: print "*" output = "[[*,*],[*"
         return
     ps (1): after first call
       output = "[[*,*],[*"
       print "," output = "[[*,*],[*,"
       call ps(0):
       ps(0):
         current output "[[*,*],[*,"
         n == 0: print "*" output = "[[*,*],[*,*"
         return
    ps(1): after second call
       output = "[[*,*],[*,*"
       print "]" output = "[[*,*],[*,*]"
       return
   ps(2): after second call
       output = "[[*,*],[*,*]"
       print "]" output = "[[*,*],[*,*]]"
       return

Final output: "[[*,*],[*,*]]"

Thank you for your help just what I needed – Jason Mar 22 '17 at 22:59 — Jason, Mar 22 '17 at 22:59

score 0 · Answer 2 · answered Mar 22 '17 at 22:26

0

Well, you probably heard the terms stack frame and call stack already. They are quite important to understand what happens in a recursion.

My tip is to draw the stack frames in a tree, according to their invocation.

In this case it would look like:

ps(2)
  |
  |--ps(1)
  |    |
  |    |--ps(0)
  |
  |--ps(1)
  |    |
  |    |--ps(0)

Now add to this the output from each invocation, and you should be fine.

As mentioned, on future questions try to explain what you expect or what you are trying to achieve.

answered Mar 22 '17 at 22:26

Ramzi Khahil

4,932
4
35
69

Call stack yes stack frame no better back up it sounds like – Jason Mar 22 '17 at 23:08
Have a look here http://stackoverflow.com/questions/10057443/explain-the-concept-of-a-stack-frame-in-a-nutshell -- Basically, it is the information passed to an invocation of a funtion, the most interesting part are the parameters, but it also includes stuff like a return address (what code should be executed when done) and an address where to put the return value (if it is not void) and such. The last two are normally taken for granted, but usefull to look at when learning recursion. – Ramzi Khahil Mar 23 '17 at 09:27

Java recursion output different from expected

2 Answers2