The Big Programming Thread - Page 86

A recursive function might call itself with different parameters to compute its return value, that's all.

For example, factorial calculation:

public class Main
{

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

	public static int factorial (int n)
	{
		if( n == 0 ){
			return 1;
		}
		return n * factorial(n - 1);
	}

}

Another common example, calculating the Fibonacci number:

public class Main
{

	public static void main (final String[] args)
	{
		System.out.println(fibonacci(7));
	}

	public static int fibonacci (int n)
	{
		if( n == 0 ){
			return 0;
		}
		if( n == 1 ){
			return 1;
		}
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

}

Recursion is a general idea for creating methods. A recursive method has a simple answer for some base case, and calls itself for any other cases. The recursive calls generally try to whittle the problem down to a base case, then merge the returns of each call.

The Fibonacci and the factorial example, while being relatively easy to understand, are computationally very slow. There are much faster algorithms that don't use recursion.

Recursion just means a method calls itself until it reaches some sort predetermined value. In this case, the method calls itself until it reaches zero. Since it calls itself there's only ever one of it, so it's static.

public class Main
{
             
        public static void main (final String[] args)
        {
               GetToZero(7);
         }

	public static void GetToZero (int n)
	{
            if(n == 0)
            {
                System.out.println("Reached Zero");
            }
            else if (n > 0)
            {
                System.out.println("Subtracting 1 - " + n);
                n--;
                GetToZero(n);
            }
            else if (n < 0)
            {
                System.out.println("Adding 1 - " + n);
                n++;
                GetToZero(n);
            }
        }
}

First thing to recognize: programming is problem solving by decomposition. Given a problem, you decompose that problem repeatedly into smaller problems until the subproblems are manageable to solve on their own. For example, the problem of cooking spaghetti involves several subtasks such as buying the ingredients, preparing the sauce, preparing the meat, and the mixing it all together. In code, you typically use functions/methods to realize this decomposition, e.g.,

void cookSpaghetti() {
    buyIngredients();
    prepareSauce();
    prepareMeat();
    mixIngredients();
}

With that in mind, recursion is a problem solving technique in which you recognize that the subproblems that you create are actually smaller versions of the original problem that you are trying to solve.

To make this more concrete, imagine a line of folk waiting for the release of heart of swarm:

front <(^^)> <(^^)> <(^^)> back

Now imagine that the person in the back of line is trying to figure out what place they are in line. One thing they can do is step out of line and count the number of people in front of them directly. However, instead of risking losing their place in line, they can ask the person in front of them:

front <(^^)> <(^^)> <(^^)> back
                       |-- "What place are you in line?"

Now, the person in front of them is posed with a similar question, so they can ask the person in front of them the same question:

front <(^^)> <(^^)> <(^^)> back
               |       |-- "What place are you in line?"
               |-- "What place are you in line?"

Finally the question is posed to the person in the front of the line. He's know he's #1, so he tells the person behind him.

front <(^^)> <(^^)> <(^^)> back
        |      |       |-- "What place are you in line?"
        1      |-- "What place are you in line?"

With that answer, the person behind the first in line now knows what place they are in line. They know they're second by adding one to the place of the person in front of them.

front <(^^)> <(^^)> <(^^)> back
        |      |       |-- "What place are you in line?"
        1      2  

And finally the person in the back knows their place in line given the position of the person in front of them by adding one.

front <(^^)> <(^^)> <(^^)> back
        |      |       |
        1      2       3

This is the essence of simple recursion:

• A base case that handles the situation when the problem we're trying to solve is directly solvable.
  
• A recursive case that solves the current problem by solving an identical subproblem of a smaller size.
  

Let's extend this to a code example that people have mentioned already, factorial(n).

int factorial(int n) {
    // Base case, i.e., front of the line: 0! = 1
    if (n <= 0) {
        return 1;
    // Recursive case, i.e., the middle or the line: n! = n * (n-1)!
    } else {
        return n * factorial(n-1);
    }
}