java version "1.8.0_92" I have the following code I am trying to understand and trace.
The part I don't understand is the * a at the end. When does that multiplication get called? And what is the return value of power1(a, n - 1);
Is it n - 1 * a
public static double power1(double a, int n) { double result; if(n == 0) { return 1; } else { result = power1(a, n - 1) * a; return result; } } You can modify the code to print a trace of the recursion. That can help you understand what is going on.
/** * Print string form of `o`, but indented with n spaces */ private static void printIndented(int n, Object o) { while (n-->0) System.out.print(" "); System.out.println(o); } /* * Added a third param `d` to keep track of the depth of the recursion */ public static double power1(double a, int n, int d) { // Entering a "possible" recursive call printIndented(d, "call power1, a=" + a + ", n=" + n + ", d=" + d); double result; if(n == 0) { // Returning from the base case, this should have the largest depth. printIndented(d, "return 1.0"); return 1; } else { result = power1(a, n - 1, d + 1); // Return from intermediate recursive calls, we print // the value of power1(a, n-1) as well. printIndented(d, "return " + result + " * " + a); return result * a; } } public static void main(String [] args) { System.out.println(power1(1.4, 3, 0)); } Output
call power1, a=1.4, n=3, d=0 call power1, a=1.4, n=2, d=1 call power1, a=1.4, n=1, d=2 call power1, a=1.4, n=0, d=3 return 1.0 return 1.0 * 1.4 return 1.4 * 1.4 return 1.9599999999999997 * 1.4 2.7439999999999993 As you can see, the value from the inner return becomes the result in the outer return statement.
We can see that power1 is defined as public static _double_ power1(double a, int n) This means that on the line
result = power1(a, n - 1) * a;
the type will be :
double = double * double;
We start our function with n and a. a will be constant in this implementation. It's given straight as to the next recursive call.
Yet n varies.
We call power1(a,n). It checks first if n == 0; It is not. So we go to the else part of the if. Time to calculate result.
To know what the value of result is, we need power1(a,n-1). We proceed. n-1 can be 0 or can not be.
If it's 0, we return 1, and we now know that power1(a,n-1) = 1. We can now multiply it with a.
If it's not 0, then we need a new result, seeing as we're in a completely seperate call of the power1 method. We now need power1(a,n-2). We check again for 0. If n-2 == 0, return 1 to get the caller to calculate power(a,n-1). If not go down another call, now with n-3... Etc
It's gonna call all the (n) recursive calls first, before doing n multiplications.
If you call power1 with a = 2 and n = 3, this is what will happen:
result = power1(2, 2) * 2;
power1(2, 2) = power1(2, 1) * 2;
power1(2, 1) = power1(2, 0) * 2;
power1(2, 0) = 1
In the above example, the * a happens three times in total. It is called whenever power1(a, n) returns a value. The first power1(a, n) to return a value will be power1(2, 0) (this is because n = 0 is your "base" case). Then power1(2, 1) will return 2. Then power1(2, 2) will return 4. Then your initial call to power1(2, 3) will return 8.
First you call power (a,n-1) until n == 0 which is your base case .
Then the 1 gets returned and is multiplied by the value of a. Then a is returned to the previous call where it is multiplied by a . The process is repeated N times and thus you get A^n. I would recommend you go throught one example of this code giving it some initials values and tracing the code using pen and paper.
double (from the recursive call) * double a, so that mean you get a double back, which is exactly as the method power1 defines.