1. Member Join Date
Sep 2012
Posts
54
Rep Power
0 Recursion Help!

Java Code:
// A simple example of recursion.
class Factorial {
// this is a recursive method
int fact(int n) {
int result;
if(n==1) return 1;
result = fact(n-1) * n;
return result;
}
}
class Recursion {
public static void main(String args[]) {
Factorial f = new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
Output:
Java Code:
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120
The book calls it a recursion/recursive the process of defining something in terms of itself.
But i can't understand this recursion and i want to learn it because it will be vital in my programming skills.
Can someone explain to me what's going on to this code?  Reply With Quote

2. Re: Recursion Help!

Please edit your post first and give your code regular and consistent indentation. It's very hard to understand code that is poorly formatted, especially when it is someone else's code.  Reply With Quote

3. Senior Member Join Date
Jan 2009
Location
CA, USA
Posts
271
Rep Power
11 Re: Recursion Help! Originally Posted by Fubarable Please edit your post first and give your code regular and consistent indentation. It's very hard to understand code that is poorly formatted, especially when it is someone else's code.
It's relatively short and not hard to understand at all... that being said, the code tags on this forum are not always forgiving with indentation. I feel like it's better to just help out, instead.

---

Anyway,

Recursion, in a mathematical sense, is when a function is defined in terms of itself, or basically when the function contains a reference to itself. Therefore, a recursive function can be reduced to a simpler version of itself all the way down to a base case. Let's take a look at the factorial function

f(n) = 1 for n = 0
f(n) = n * f(n-1) for n > 0

As you can see, the function f is included in the definition itself. And there is a base case where the recursion stops (in this case, when n = 0).

So, f(3) can be rewritten as
f(3)
= 3 * f(2)
= 3 * 2 * f(1)
= 3 * 2 * 1 * f(0)
= 3 * 2 * 1 * 1
= 6

Now when you look at it from a programmatic perspective, you can see a very similar thing going on. I'll comment your code to show you were they line up.

Java Code:
class Factorial
{
int fact(int n) // f(n)
{
int result;
if(n == 1) // f(n) = 1 for n = 1
return 1;
result = fact(n - 1) * n; // f(n) = n * f(n-1) for n > 1
return result;
}
}
And, when java runs through this code it is essentially saying
fact(n)
= fact(n-1) * n
= fact(n-2) * fact(n-1) * fact(n) ...

So it's saying
in order to compute the factorial of 3, I require the factorial of 2
in order to compute the factorial of 2, I require the factorial of 1
in order to compute the factorial of 1, I require the factorial of 0
I have the factorial of 0, now I can compute the factorial of 1
...
...
back up to factorial of 3

Is there any particular part of this you need a more in depth explanation for?
Last edited by AndrewM16921; 06-24-2013 at 04:36 AM.  Reply With Quote

4. Senior Member Join Date
Apr 2013
Location
Sweden
Posts
272
Rep Power
7 Re: Recursion Help!

Recursion is extremely difficult to grasp and understand, at least for me, even did recursion in discrete maths before doing it in programming and still I have difficulties in some
more complicated problems.
The concept is basically that we reduce the problem into a smaller instance of the problem to which we know the answer, in this case n = 1, and the function calls itself as many times as needed until reaching the answer that
we know.

btw, the factorial example that we all have seen, doesn't it get a stack overflow if one calls fact(0) ?  Reply With Quote

5. Senior Member Join Date
Jan 2009
Location
CA, USA
Posts
271
Rep Power
11 Re: Recursion Help! Originally Posted by superhaNds btw, the factorial example that we all have seen, doesn't it get a stack overflow if one calls fact(0) ?
The proper base case for factorial is n=0, then it should throw an IllegalArgumentException or something like that when n < 0. Kinda skipped over that for the sake of explaining recursion itself =p  Reply With Quote

6. Re: Recursion Help! Originally Posted by superhaNds Recursion is extremely difficult to grasp and understand, at least for me
Recursion is extremely easy to understand if you're lazy (like me); all you have to do is take care that your recursive function/method doesn't have side effects; the rest is just a direct implementation of the recursive formula you found in a book ...

kind regrds,

Jos  Reply With Quote Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•