We have seen how to define functions (and how to use if statements). We can use functions to calculate any values, if we use recursion; that is if we allow functions to call themselves.
This may seem weird, but notice you already use a similar concept in regular life; for example, if you work, you have to listen to your boss, and your boss’s boss, and so on; the relationship boss is recursive. Same with ancestor, and in computers, a folder or directory contains other folders etc
When you call a function in Java, it evaluates the function and yields a value; it doesn’t care which function you called; so, if we call the same function, it is ok.
1. Factorial
The standard example is the factorial function, which can be defined as 1*2*3*…*n, or, recursively as:
n! = n * (n-1)! and 0! = 1 (so we know where to start).
We can define this function in Java as:
public int factorial(int n) {
if(n<=0)
return 1;
else
return n*factorial(n-1);
}Notice that, since this definition doesn’t cover the factorial of negative numbers, and I’m paranoid, I’m using ⇐0 as my condition.
Imagine that we try to calculate factorial(4), the execution will go as follows:
-
factorial(4) ⇒ is n⇐0 ? no (it is 4), then return 4*factorial(3) ; ok , let’s calculate factorial(3) …
-
factorial(3) ⇒ is n⇐0 ? no (it is 3), so return 3*factorial(2) ; ok, let’s calculate factorial(2) …
-
factorial(2) ⇒ is n⇐0 ? no (it is 2), so return 2*factorial(1) ; ok, let’s calculate factorial(1) …
-
factorial(1) ⇒ is n⇐0 ? no (it is 1), so return 1*factorial(0) ; ok, let’s calculate factorial(0) …
-
factorial(0) ⇒ is n⇐0 ? yes ! so return 1 (and the whole stack unravels)
2. Power
As another example, let’s define the power function, that raises a base to an exponent; raising 2 to the 3rd power would be 2x2x2=8 (we’re multiplying 2 three times).
We can define it recursively as: pow(base, exponent)= - 1 if exponent = 0 (anything to the 0th power is 1 by convention) - base * pow(base, exponent-1) otherwise
Or in Java:
public int pow(int base, int exponent) {
if(exponent<=0)
return 1;
else
return base*pow(base,exponent-1);
}2.1. Quick check
+ Can you trace how would we calculate pow(3,2) ? How about pow(4,3) ?
3. Usual form
As you can see from the examples above, in recursive functions we need:
-
one or more base cases, where we know the result or can calculate it without a recursive call.
-
one or more recursive calls , where we call the same function, but with different parameters; we need to change the parameters so that we get closer and closer to the base case, so we eventually get to the base case.
Many times, we will add or subtract one from the parameter, to get the next level. This allows us to go through all the integers, counting. I tend to be paranoid when writing recursive functions, so my base case tends to include numbers that would be outside the usual range of a function (for example, in factorial I check whether n⇐0, rather than just n==0).
4. Counting and printing
For example, let’s define a function that prints all numbers counting down to 0; it takes one parameter, so if we call it with 10 it would do the standard countdown: 10,9,8,7,6,5,4,3,2,1,0. If we reach 0, we know we’re done. Otherwise, we print the current number, and call again with the next number down, until we reach 0.
public static void printCountDown(int from)
{
if(from<0)
return;
else {
System.out.println(from);
printCountDown(from-1);
}
}4.1. More counting
As another example, here’s counting up, from a given number, by a given step. We stop when we reach to.
void PrintCountUp(PrintStream out, int from, int to, int step) {
if(from<=to) {
out.println(from);
PrintCountUp(out, from+step, to, step);
}
}5. Accumulators
Many times, when we use recursive functions to calculate values, we can pass our function an extra parameter, and use it to accumulate the current value (we call this extra parameter an accumulator). For example, we could write the power function with an accumulator as follows (changing the name so we can distinguish between them):
public static int pow_accum(int base, int exponent, int current) {
if(exponent<=0)
return current;
else
return pow_accum(base,exponent-1, current*base);
}In this case, if the exponent is 0, we are done, and we return the current accumulated value; otherwise, we call ourselves, decrementing the exponent, and multiplying the accumulator by the base. In the end, we would have multiplied that accumulator by the base the required number of times.
Notice this function takes three arguments, instead of two, and would need to be called with an initial value of 1 for current. We can make sure it is called the right way, by defining a wrapper function, that just calls our function with the appropriate initial value, as follows:
public static int pow_accum(int base, int exponent)
{
return pow_accum(base, exponent, 1);
}6. Recursion by half
Although most of our simple examples will just increment or decrement our parameter, we can do other operations; one that is particularly useful is dividing our range by half (since this will make our operations much faster).
For example, we can define power as follows:
-
pow(base, exponent) equals:
-
1 if n is 0 (or ⇐0)
-
pow(base, exponent/2) * pow(base, exponent/2) if exponent is even
-
base * pow(base, exponent/2) * pow(base, exponent/2) if exponent is odd
-
In Java, this would look like:
int pow(int base, int exponent)
{
if(exponent<=0) {
return 1;
}
else if (isEven(exponent)) {
int halfPow=pow(base, exponent/2);
return base * halfPow * halfPow;
} else { // it is odd
int halfPow=pow(base, exponent/2);
return base *halfPow * halfPow;
}
}The great thing about this function is that we are doing much less work; with the functions above, if we need to raise something to the 1,000 power, we
7. Characters in a string
We saw that we can obtain a string’s lenght by using the .lenght method, and we can use charAt to get the character at a given place. Given this, we can create functions that go over all the characters in a string, by going through all the numbers from 0 to length-1, and using charAt to get the corresponding character; for example, we can write a function to check whether a character is in a string:
// returns true if the string contains the character
// we start looking at the char with index from (so if from is 3, we just care whether the string
// contains the c in its 4th through last characters
private static boolean stringContains(String s, char c, int from)
{
if(from>=s.length())
return false;
else if (s.charAt(from)==c)
return true;
else
return stringContains(s,c,from+1);
}Notice this function has two base cases; one for when we find the character (and so we return true), and another for when we get to the end of the string (and so retur false, since we didn’t find the character).
Also, this functions takes an extra argument, from, representing the index of the current character; since that is not useful to the caller of the function, we write a wrapper function, that calls our recursive function with the right initial index.
public static boolean stringContains(String s, char c)
{
return stringContains(s,c,0);
}8. Summary
-
A recursive function is one that calls itself.
-
We normally define a recursive function with:
-
one or more base cases, where we know the answer (or can calculate it without using recursion)
-
one or more recursive calls, where we call the same function, but with different values for the parameters.
-
-
If our recursive function needs extra arguments, we write a wrapper function that calls the recursive one with extra arguments.
9. Exercises
-
Define a function printCountDown that takes two integers, say
fromandto(assuming from is bigger than to), and prints all the numbers between from and to (including both from and to). -
Define a function printCountUp that takes two integers, say
fromandto(now assuming from is smaller than to), and prints all the numbers between from and to (including both from and to).