• 0

Recursion


Question

Hi guys. Learning some Java and came across the subject of recursion. There was a snippet of code here which is basically recursion at play:

 

 
public class main {
public static void main(String[] args) {
 
long num;
 
num = fact(5);
 
System.out.println(num);
 
}
 
public static long fact(long n) {
if(n <= 1) 
return 1;
else
return n * fact(n-1);
}
}
Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 0

The running total is held on the stack. Every time a function is called, it pushes a new "frame" on the stack (memory region holding its parameters and local variables), and every time a function returns, it pops its frame from the stack. A simple program like this:

void sayHello() { System.out.println("Hello"!); }

void main() { SayHello(); }
Executes like so:
main()
     -> sayHello()
              -> System.out.println("Hello");
                     -> (... unknown implementation of println ...)

Your function fact() calls itself until the value passed is 1, so it executes like so:

fact(5)
    -> fact(4)
           -> fact(3)
                  -> fact(2)
                         -> fact(1)

fact(1) evaluates to 1 and returns.

fact(2) evaluates to 2 * fact(1), which is now 2 * 1. It returns 2. 

fact(3) evaluates to 3 * fact(2), which is now 3 * 2. It returns 6.

etc.

hence fact(5) evaluates to 120.

 

As you can see, there is no variable in the program that explicitely holds the running total; rather it is an implicit variable held on each stack frame representing the return value of each function call. It is a bit hard to understand until you do some assembly and see how this happens under the hood.

 

The stack is a very limited memory region - typically 1MB. Abusing recursion is the most typical way of blowing up the stack, a bug referred to as a stack overflow.

  • Like 2
Link to comment
Share on other sites

  • 0

 

Hi guys. Learning some Java and came across the subject of recursion. There was a snippet of code here which is basically recursion at play:

 
public class main {
public static void main(String[] args) {
 
long num;
 
num = fact(5);
 
System.out.println(num);
 
}
 
public static long fact(long n) {
if(n <= 1) 
return 1;
else
return n * fact(n-1);
}
}

Stop repeating yourself....

Not sure if there is a question in here.. but basically recursion is the act of repeating..

so like

private void main()
{
   minusTo1(100);
}


private void minusTo1(int num)
{
  //Check if num - 1 == 1. 
  if (--num != 1)
    return minusTo1(num);
  else
    return 1;
}

 

Link to comment
Share on other sites

  • 0

did ask for an explantion (apparently, it decided to delete that massive paragraph I wrote for some strange reason) on how this code actually works as I wasn't sure how exactly the method managed to return 120 as I couldn't see where the multiplication was actually happening, even in the debugger I couldn't see a hidden variable holding the total figure as it went around. Also, I wasn't entirely sure how exactly it worked. 

 

I believe Firey's example helps me get the concept of recusion better, but I still don't understand where exactly it did the multiplication or where the variable was held?

Link to comment
Share on other sites

  • 0

did ask for an explantion (apparently, it decided to delete that massive paragraph I wrote for some strange reason) on how this code actually works as I wasn't sure how exactly the method managed to return 120 as I couldn't see where the multiplication was actually happening, even in the debugger I couldn't see a hidden variable holding the total figure as it went around. Also, I wasn't entirely sure how exactly it worked. 

 

I believe Firey's example helps me get the concept of recusion better, but I still don't understand where exactly it did the multiplication or where the variable was held?

Recursion is basically the act of repeating a function until a desired result is met.  I personally use it for retries.  Instead of having to duplicate code.  I will re-call a function (that I am in) to preform a retry.  Kind of like:

int retries = 1;

SendMyData(string data)

{

    //try to send data

    

    //if it fails, check if retries > 0, if so -1 from retries

   //and call SendMyData() passing in the data we got the first time

   

   //if retries is 0, then don't do anything

}

Because reties will already be set to 0, we will not run the function again after it is called the second time.

And because we don't have any code at the bottom to run, it won't duplicate anything.

Link to comment
Share on other sites

  • 0

all lies in this line :

return n * fact(n-1);

return will be done when "all" calculation on the right will be finished, as it's a recursive function that "terminates" (and returns 1) when n is lower or equal than 1. The actual calculation is this one :

 

fact(5) => return ((((5 * fact(4)) * fact(3)) * fact(2)) * 1;

 

As everything is a multiplication in this case, it's equal to 5 * 4 * 3 * 2 * 1 = 120 

 

Hope it helps :) (and that i didn't get anything wrong :P...)

  • Like 2
Link to comment
Share on other sites

  • 0

Ah, okay! I think I have finally understood it all now :D Many thanks to both of you, you definitely explained it to me well :D 

Link to comment
Share on other sites

  • 0

fact(5) => return ((((5 * fact(4)) * fact(3)) * fact(2)) * 1;

Well technically this is not correct. The calculation is 5 * 4 * 3 * 2 * 1, not 5 * fact(4) * fact(3) * fact(2) * 1, which would give a much larger number.

 

A more correct and graphical way of putting it would be:

fact(5) = 5 * fact(4)
              fact(4) = 4 * fact(3)
                            fact(3) = 3 * fact(2)
                                          fact(2) = 2 * fact(1)
                                                        fact(1) = 1
Link to comment
Share on other sites

  • 0

Asik, as always you've saved the day! I had learned about the stack before but my programming has gotten rusty and... yeah, I guess I had forgotten about that  :laugh:

 

It now makes perfect sense. Many thanks!

Link to comment
Share on other sites

This topic is now closed to further replies.