Results 1 to 6 of 6
Thread: Recursion Help!
 06232013, 04:41 AM #1Member
 Join Date
 Sep 2012
 Posts
 41
 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(n1) * 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)); }
Java Code:Factorial of 3 is 6 Factorial of 4 is 24 Factorial of 5 is 120
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?

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.
 06232013, 05:17 AM #3Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 268
 Rep Power
 7
Re: Recursion Help!
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(n1) 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(n1) for n > 1 return result; } }
fact(n)
= fact(n1) * n
= fact(n2) * fact(n1) * 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; 06242013 at 04:36 AM.
 06232013, 05:53 PM #4Senior Member
 Join Date
 Apr 2013
 Location
 Sweden
 Posts
 272
 Rep Power
 3
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) ?
 06242013, 04:34 AM #5Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 268
 Rep Power
 7
 06242013, 09:08 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,071
 Blog Entries
 7
 Rep Power
 24
Re: Recursion Help!
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,
JosThe only person who got everything done by Friday was Robinson Crusoe.
Similar Threads

Recursion?
By Fingerz in forum New To JavaReplies: 10Last Post: 01082011, 03:25 AM 
more fun... with recursion
By sonny in forum New To JavaReplies: 19Last Post: 03232010, 06:09 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
Recursion
By Mika in forum New To JavaReplies: 5Last Post: 01042009, 02:13 AM
Bookmarks