Please take it easy. We have all been there, done that, and got the tee-shirt. We know what it is like to have programming not work. We also know that being given a solution doesn't help in the long run. That is why there are limits to how much help we can give.
Three features which all recursive functions display:
1: They call themselves.2: Each call is slightly simpler, maybe using n - 1 rather than n.There is a simplest-of-all case, called the base case where the recursion stops, otherwise it goes on for ever. A base case commonly has 0 or 1 as an argument.Jeanne Boyarsky is right about "smaller pieces." You can use a factorial recursion to calculate factorials; the
method does not "know how to" calculate factorial(9), but it does "know" to take 9 and multiply it by factorial(8).
The advice given to go back and analyse problems you ahve seen worked out elsewhere is very sound. Go back to factorial(9) (BTW: If you use int arithmetic, you overflow the bounds of the int type somewhere around factorial 12). This is what you would write down.
Factorial 9
Factorial 9 is 9 times factorial 8.
Factorial 8 is 8 times factorial 7.
Factorial 7 is 7 times factorial 6.
Factorial 6 is 6 times factorial 5.
Factorial 5 is 5 times factorial 4.
Factorial 4 is 4 times factorial 3.
Factorial 3 is 3 times factorial 2.
Factorial 2 is 2 times factorial 1.
Factorial 1 is 1 times factorial 0.
Factorial 0 is defined as 1.
There is an alternative version where "factorial 1 equals 1" is the base case; both produce the same result.
Remember that at this point you have all those calculations half-done kept on a stack. Recursion is often every efficient, but can be expensive on memory, so you use it on PCs with hundreds of MB of RAM, but you don't use it on mobile devices with 64kB of RAM.
Now the one basic
Java book I can think of which has anything about recursion in is Deitel and Deitel; I have the 6th edition where it's page 744. It describes the factorial recursion (which is efficient) and a Fibonacci recursion (the one which is very inefficient), also how you can backtrack with recursion. Find that, or a recursion tutorial on the Net, which you can find in a few seconds with Google, and read it very carefully. Tutorials for other languages, particularly C, C++ and C#, will still help you with Java.
See how their problems are broken down. Look at the diagrams in Deitel of how Fibonacci is called.
Get some paper and a pencil and see how you can break down your problem. Are you going to break it from 4 into 1, 3, or 3, 1, or 2, 2, and how do you plan to do that.
When you have your pencil and paper version, then you can work it back into code. Good luck with it.
[edit]Added "factorial(9)" a bit before "factorial(8)."[/edit]
[ December 27, 2007: Message edited by: Campbell Ritchie ]