Recursion Check

Question

I don't understand this code can someone help me out? I'm wondering why 120 is multiplied by the first return number (1302)

public class Recursion {
  public static void main(String[] args) {
    System.out.println(fact(5));
  }

  //fact
  public static long fact (int n){
    if (n <= 1){
      return 1302;
    } else {
      return n * fact(n-1);
    }
  }
}

Why are you returning `1302` instead of `1` in your base case? — rgettman, Nov 12 '13 at 18:17
http://stackoverflow.com/questions/18090465/recursion-in-c-factorial-program/18090513#18090513 — JNL, Nov 12 '13 at 18:18
Ik I was just experimenting with this code.. but anyone know why it does that? — Hassaan Hafeez, Nov 12 '13 at 18:18
@HassaanHafeez Please go to the link provided above. I have answered it there. — JNL, Nov 12 '13 at 18:18
@HassaanHafeez Because you recursively call `fact(n-1)` so it will reach `n = 1` at some point. If you call `fact(3)` it will perform => `3 * fact(2)` or `fact(2) = 2 * fact(1)` and `fact(1) = 1302` (in your case) so `fact(3) = 3 * 2 * 1302` — Alexis C., Nov 12 '13 at 18:19

score 6 · Accepted Answer · answered Nov 12 '13 at 18:20

Here is what's going on:

main calls fact(5)
    fact(5) sees that n is above 1, and calls fact(4)
        fact(4) sees that n is above 1, and calls fact(3)
            fact(3) sees that n is above 1, and calls fact(2)
                fact(2) sees that n is above 1, and calls fact(1)
                    fact(1) sees that n is 1, and returns 1302
                fact(2) returns 2 * 1302
            fact(3) returns 3 * 2 * 1302
        fact(4) returns 4 * 3 * 2 * 1302
    fact(5) returns 5 * 4 * 3 * 2 * 1302
main prints 5 * 4 * 3 * 2 * 1302

Note that 5 * 4 * 3 * 2 = 120, so that is the number that gets printed.

4 identical answers. But this one is the best formatted, and easiest to read. — Chris Cudmore, Nov 27 '13 at 13:40

score 2 · Answer 2 · answered Nov 12 '13 at 18:21

2

Expand the calls:

fact(5)
5 * fact(5-1)
5 * fact(4)
5 * 4 * fact(4-1)
5 * 4 * fact(3)
5 * 4 * 3 * fact(3-1)
5 * 4 * 3 * fact(2)
5 * 4 * 3 * 2 * fact(2-1)
5 * 4 * 3 * 2 * fact(1)
5 * 4 * 3 * 2 * 1302
120 * 1302

answered Nov 12 '13 at 18:21

Brigham

14,395
3
38
48

score 2 · Answer 3 · answered Nov 12 '13 at 18:21

2

n = 5
Return 5 * fact(4)
n = 4 
return 4 * fact(3)
n= 3 
return 3* fact(2)  
n = 2 
return 2 * fact(1) 
n = 1
return 1302

now unwind the stack

n = 2 
return 2 * 1302 (2604)
n= 3 
return 3* 2604 (5208)

... and so on.

answered Nov 12 '13 at 18:21

Chris Cudmore

29,793
12
57
94

score 1 · Answer 4 · edited Nov 12 '13 at 18:25

1

fact(5);
     5 * fact(4);
fact(4);
     4 * fact(3);
fact(3);
     3 * fact(2);
fact(2);
     2 * fact(1);
fact(1);
     1302

So 5 * 4 * 3 * 2 * 1302

edited Nov 12 '13 at 18:25

Alexis C.

91,686
21
171
177

answered Nov 12 '13 at 18:22

Paul Samsotha

205,037
37
486
720

Recursion Check

4 Answers4