Recursion
Recursion
We say that a method is recursive when it calls itself.
A good analogy would be when we define a word with the word itself. Take a look at this example:
companion: A person who accompanies or associates with another; a comrade.
In algebra: composite function f(f(x))
A recursive program requires two parts:
1. The non-recursive part, the base case, which lets the recursion eventually end.
2. The recursive part: calling itself.
Indirect recursion: a method invokes another method, eventually resulting in the original method being invoked again.
Recursion vs. Iteration
There is always a non-recursive solution for all the problems done in this chapter. Recursion has the overhead of multiple method invocations and, in many cases, presents a more complicated solution than its iterative counterpart.
A programmer must learn when to use recursion and when not to use it. Determining which approach is best depends on the problem being solved. All problems can be solved in an iterative manner, but in some cases the iterative version is much more complicated. Recursion, for some problems, allows us to create relatively short, elegant programs.
An example of a recursive method to calculate the factorial of a number:
public int factorial(int num)
{
if ( num "less than or equal to" 1 ) return 1;
else return (num * factorial(num-1));
}
Classwork:
Visit edmodo.com to work on the following exercises.
1. Write a class, NSum_YI.java that recursively calculates the sum of numbers 0 to N. Write a driver to test your program.
2. Use paper and pencil
Write a recursive definition of x^y (x raised to the power y), where x and y are integers and y less than or = 0. Trace your recursive definition for x = 2 and y = 3 similar to the illustration above.
3. Write a recursive definition of i * j (integer multiplication), where i less than 0. Define the multiplication process in terms of integer addition. For example, 4 * 7 is equal to 7 added to itself 4 times.