Recursion - Can't Understand This Simple Arithmetic in Java

Question

I am studying old examination papers from my university to be able to prepare for my upcoming exams. Everything is easily understandable from the simplest problems to the most complicated ones. However, I can not, for the life of me, figure the following one out.

class k{
    static int g(int n) {
        if (n==0){
            return 1;
        } else {
            return 2*g(n-1);
        }
    }
    public static void main(String[] args) {
        System.out.println(g(3));
    }
}

Why does this code return 8 as an answer. I get that its basically a power function where the number input is calculated as 2 to the power of that number and hence the answer in this case is 8. But what is really going on. I don't get it. Could someone please explain it in simple English? I'd really appreciate it.

By the way, the question only asks what the output is, not why. But I would feel more comfortable if I knew why it is the way it is.

PS: The reason people are giving answers using 5 as an example is that I had mistakenly put 5 instead of 3 in the code above, which I have corrected now.

Best way to approach this is to "play computer": Trace out precisely what happens using pencil and paper. Indent your notes per-call. Easiest way to grok recursion. — Dave Newton, Apr 27 '12 at 17:46
@ThomasOwens Thank you, the program in the exam paper had 3 as its value, I forgot that I had left the 5 there from my testing. I have corrected it now. — Nico, Apr 27 '12 at 17:49
Thank you for the answers everyone. And I apologize for the confusion about whether it was 5 or 3. — Nico, Apr 27 '12 at 18:05
The temptation to post an answer that linked back to the question was almost impossible to resist, but I guess someone's already done that one :) — Martin James, Apr 27 '12 at 20:54
Possible duplicate of [Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion) — , May 18 '16 at 11:34

score 3 · Accepted Answer · answered Apr 27 '12 at 17:46

3

This is called recursion. Unless n is ZERO, reduce n by 1 and multiply it by two.

return 2 * g(5-1)

return 2 * g(4-1)

etc..,

answered Apr 27 '12 at 17:46

kosa

65,990
13
130
167

score 2 · Answer 2 · answered Apr 27 '12 at 17:55

2

Recursive like everybody said, but there seems to be some confusion about the initial value of n. It's 3 in the example.

g(3) = return 2 * g(2);

g(2) = return 2 * g(1);

g(1) = return 2 * g(0);

g(0) = return 1;

i.e. 2 * 2 * 2 * 1 = 8

answered Apr 27 '12 at 17:55

grahaminn

1,557
1
10
10

3

It's `3` *now*, but it wasn't originally. – Dave Newton Apr 27 '12 at 17:55

Amir Raminfar · Answer 3 · 2012-04-27T18:08:26.893

1

You should study on recursion. The above example does 2 ^ n. So for n=4 you get 16.

edited Apr 27 '12 at 18:08

answered Apr 27 '12 at 17:51

Amir Raminfar

33,777
7
93
123

Actually, it computes 2^n, not 2^(n+1). So, for instance, `g(0) == 1` and `g(1) == 2`. – Ted Hopp Apr 27 '12 at 17:57

score 1 · Answer 4 · answered Apr 27 '12 at 17:53

It's a recursive function that takes a little piece of the arithmetic at a time, and sends along the rest until some ending condition is met.

Take, for instance, the well-known factorial recursive method.

public long factorial(int n) {
     return n == 0 ? 1 : n * factorial(n-1)
}

If we call factorial(3), we need to do the following.

factorial(3) => 3 * factorial(3-1) => 3 * 2 * factorial(2-1) => 3 * 2 * 1 * factorial(1-1)

You can see the recursive expansion from here. Apply this similar tactic to your snippet of code, and you will arrive at why the answer is the way it is.

score 1 · Answer 5 · answered Apr 27 '12 at 17:57

1

g(1) = 2*g(0) = 2

g(2) = 2*g(1) = 4

g(3) = 2*g(2) = 8

g(4) = 2*g(3) = 16

g(5) = 2*g(4) = 32

g(5) would be 32. g(3) would be 8.

answered Apr 27 '12 at 17:57

None

5,491
1
40
51

Recursion - Can't Understand This Simple Arithmetic in Java

5 Answers5