Java: Recursion

This is by far the hardest concept to use for me, even if the idea seems straightforward.

Methods, in addition to being able to call other methods and variables, can call themselves, which makes for interesting ways to solve problems, often resulting in much more concise code.


public int sumOf( int n ) {
    if ( n == 0 ) return 0;
    else {
        return ( n + sumOf( n - 1 ) );
    }
}


This method returns the sum of every number from 0 up to the parameter provided. To illustrate this, use n = 2. The steps it goes through are as follows:


sumOf( 2 );              //Step 1
Parameter (2) is not 0, so return 2 + sumOf( 1 )

sumOf( 1 );            // Step 2
Parameter (1) is not 0, so return 1 + sumOf( 0 )

sumOf( 0 );            //Step 3
Parameter is 0, return 0

Place Step 3 into Step 2, result of Step 2 is 1 + 0 = 1
Place Step 2 into Step 1, result of Step 1 is 2 + 1 = 3


As we see, with every call we make not containing our base case (In this case, n == 0), the next step is required to fill in the blank. This is referred to as the call chain, and it exists whenever a function calls any other function, though it helps visualize recursion more than standard calls.

Recursion can be effectively used as a compressed for of iteration, as the above code is equivalent to


public int sumOf( n ) {
    int sum = 0;
    while ( n > 0 ) {
        sum = sum + n;
        n = n - 1;
    }
    return sum;
}


When you get recursion down, it can be faster to code than by the iterative process above, as well as being more compact, although it takes more resources to run, which is a fairly large issue with larger programs.

Play around with it, and try to get a feel for what it does. No Java post on Monday, I'll be off for a couple of days.