CODEWITHSUNDEEP
javarecursion
ShGulia
ShGulia

Reputation:

JAVA Recursive Program logic

public class Prod {
    public static void main(String[] args) {
        System.out.println(prod(1, 4));
    }
    public static int prod(int m, int n) {
        if (m == n) {
            return n;
        } else {
            int recurse = prod(m, n-1);
            int result = n * recurse;
            return result;
        }
    }
}

On running the above code , I get 24 ? I don't quite understand how?

My doubts: 1. When m =1 , n=4 , we call prod until m and n become equal to 1. Then the output should be n and else block should not be executed??

Someone please help me understand the logic.

Upvotes: 0

Views: 2438

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109593

prod(1, 4);

public static int prod(int m, int n) {
    if (m == n) {
        return n;
    } else {
        int recurse = prod(m, n-1);
        int result = n * recurse;
        return result;
    }
}

can be transformed with m == 1 to:

prodA(4);
public static int prodA(int n) {
    if (1 == n) {
        return n;
    } else {
        int recurse = prodA(n-1);
        int result = n * recurse;
        return result;
    }
}

which has a transformation (head recursion):

public static int prodA(int n) {
    int result = 1;
    while (n > 1) { // Actually n != 1
        result *= n;
        --n;
    }
    return result;
}

which is the factorial function.

Upvotes: 0

vonbrand
vonbrand

Reputation: 11831

To understand any program with functions, you assume the called functions do their job right, and check that the calling function calls them in the correct order with the correct arguments, and combines the results correctly.

For recursive functions you need to check that each recursive call gets you closer to the case in which there is no recursion.

Here nobody told us what is the result supposed to be. The recursion ends whenever m == n, and the recursive call is with n = n - 1, so this will work only if m <= n.

Consider a string of calls, each one reduces n by 1, while m stays fixed. Say n == m + 3 for finding out what happens: The first call gets m + 2, the second m + 1, the third m, and returns m. The second takes n == m + 1 by m returned by the third, the second takes n == m + 2 and multiplies by the previous result, and finally the result is (m + 3) * (m + 2) * (m + 1) * m. This function computes n! / (m - 1)!, if n >= m. Knowing that this is what is going on, it is easy to check that our (up to now just) hunch is right.

Upvotes: 0

theonewolf
theonewolf

Reputation: 31

Just run through this with the numbers, you need to write it down to see the behavior exactly (in the future, I suggest adding lots of prints to your code to check variables and how they change with each pass through).

prod(1,4)
m=1,n=4
m != n so, recurse = prod(1, 3)

prod(1, 3)
m=1,n=3
m != n so, recurse = prod(1, 2)

prod(1, 2)
m=1,n=2
m != n so, recurse = prod(1, 1)

prod(1, 1)
m=1,n=1
m == n so,
return 1

returns to prod(1, 2)
recurse = 1
result = 2 * 1
return 2

returns to prod(1, 3)
recurse = 2
result = 3 * 2
return 6

returns to prod(1, 4)
recurse = 6
result = 4 * 6
return 24

Thus, your program prints 24.

Sometimes the best way to figure out a program is to mechanically go through the steps line by line, executing them in your head (or on paper to track things).

Upvotes: 1

Related Questions