# Recursion Help!

• 06-23-2013, 05:41 AM
raffs03
Recursion Help!
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:
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?
• 06-23-2013, 05:46 AM
Fubarable
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.
• 06-23-2013, 06:17 AM
AndrewM16921
Re: Recursion Help!
Quote:

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.

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?
• 06-23-2013, 06:53 PM
superhaNds
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) ?
• 06-24-2013, 05:34 AM
AndrewM16921
Re: Recursion Help!
Quote:

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
• 06-24-2013, 10:08 AM
JosAH
Re: Recursion Help!
Quote:

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