Recursive Function

Question

Given the following recursive function, what would be printed by mysterious(4)?

void mysterious(int x) {
    if (x == 0) return;
    printf(“%d ”, x);
    mysterious(x-1);
    mysterious(x-1);
}

Here is my call stack:

mysterious(4) => print 4
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(0) => print 0

Is this correct?

Somebody uses the function name mysterious in all their exam questions? :) — sje397
– sje397, Commented Dec 17, 2010 at 4:58
And what's so mysterious about it? Is compiling and running it more difficult than posting on SO? — ruslik
– ruslik, Commented Dec 17, 2010 at 5:08
OP has stated in comments that it's not homework and, anyway, homework is a meta-tag that adds nothing to the question. If questioners want help rather than answers, they will ask for help. On top of that, I'm voting this up since (1) OP at least had a crack at it first; (2) it is useful in understanding recursion and clear in intent; and (3) I like annoying drive-by downvoters :-) — paxdiablo
– paxdiablo, Commented Dec 17, 2010 at 5:21
@paxdiablo: OP could first: 1) Run it to see the actual output. 2) Use a debugger. 3) Use different values for input and observe the differences. 4) Check Wiki page about recursion. — ruslik
– ruslik, Commented Dec 17, 2010 at 5:25

riwalk · Accepted Answer · 2010-12-17 05:14:53Z

7

Because every function call makes 2 function calls in turn, you can visualize your recursion as a "tree" so to speak, and you are doing a preorder traversal on the tree.

It would look something like this:

                           4
                           |
                3----------+----------3
                |                     |
           2----+----2           2----+----2
           |         |           |         |
        1--+--1   1--+--1     1--+--1   1--+--1

The order of execution that you have is:

print the number
call the function with x-1
call the function with x-1 again

This would correspond to our "tree visualization" by doing:

print the root
traverse the left node
traverse the right node

The output would be:

    4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

edited Dec 17, 2010 at 5:14

answered Dec 17, 2010 at 5:02

riwalk

14.3k6 gold badges54 silver badges68 bronze badges

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

2 Comments

jeremysawesome Over a year ago

That's what I had thought. Would it actually not print all of these on a single line with one space between each number? There are no new line \n characters in the print statement... That's what I thought would happen - but I don't work with C much.

riwalk Over a year ago

@jeremyawesome, very observant :). I changed the output.

paxdiablo · Accepted Answer · 2010-12-17 05:20:06Z

5

Why don't you just type it in to an editor in your language of choice, compile it and run? I chose Java but that's just because I'm between CygWin installs on my box at the moment - I'd much rather be using C :-)

public class testprog {
    public static void mysterious(int x) {
        if (x == 0) return;
        System.out.print(x + " ");
        mysterious(x-1);
        mysterious(x-1);
    }
    public static void main(String args[]) {
        mysterious(4);
    }
}

This outputs the numbers:

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

Basically, what's happening is that, at each level, you print out the number then call the next level twice with the next lowest number (unless it's reached zero).

Aside: technically, you do call the next layer with zero but, since it returns straight away, it has no affect on the output.

The following diagram will hopefully illustrate this better, with different symbols representing different layers:

(4) (-------------------------------) (-------------------------------)
     {3} {-----------} {-----------}   {3} {-----------} {-----------}
          [2] [1] [1]   [2] [1] [1]         [2] [1] [1]   [2] [1] [1]

edited Dec 17, 2010 at 5:20

answered Dec 17, 2010 at 5:06

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

1 Comment

kachilous Over a year ago

That makes a lot of sense. So essentially, it's the double mysterious(x-1) that causes the next lowest number to be called twice?

thejh · Accepted Answer · 2010-12-17 04:57:04Z

2

No, it will be

mysterious(4) => print 4
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(3) => print 3
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1
mysterious(2) => print 2
mysterious(1) => print 1
mysterious(1) => print 1

because 0 will cause the function to return earlier and because of that double-call.

answered Dec 17, 2010 at 4:57

thejh

45.7k18 gold badges100 silver badges109 bronze badges

Comments

score 1 · Accepted Answer · 2010-12-17 05:13:11Z

1

No. It won't print 0 cause when x==0 it will return

Also, since you have

mysterious(x-1);
mysterious(x-1);

it will print (Fixed)

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

mysterious(x-1); doesnt change the value of x. it just calls mysterious() again, this time with the value x-1

edited Dec 17, 2010 at 5:13

answered Dec 17, 2010 at 4:56

user418748

5 Comments

kachilous Over a year ago

what does "return;" mean? I'm not used to seeing return without a statement following it.

user418748 Over a year ago

when in a void function (a function which does not return a value) using return means exit the function and return to the callee

Peter Gibson Over a year ago

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 - 4 only once and then branches out for each successive call

thejh Over a year ago

Wrong, that double-call is inside the function.

user418748 Over a year ago

@Peter,@thejh. Correct. Will fix.

Collectives™ on Stack Overflow

Recursive Function

4 Answers 4

2 Comments

1 Comment

Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related