Recursion

[The Teej]

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);
}
}

[Andre S. Veteran]

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.

[BGM]

is there a question here ? :D

[firey]

 

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;
}

 

[The Teej]

I 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?

[firey]

I 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.

[kyosuken]

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...)

[The Teej]

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 

[Andre S. Veteran]

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

[kyosuken]

@Asik

 

True, i wanted somehow to show how the recursive behaved, you did a better job than me tho :)

[astropheed Veteran]

Just make sure you have a way out of the recursive function, stacks don't go on indefinitely.

[The Teej]

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!