Sign in to follow this  
Followers 0

Recursion


12 posts in this topic

Posted

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

Share this post


Link to post
Share on other sites

Posted

is there a question here ? :D

Share this post


Link to post
Share on other sites

Posted

 

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

 

Share this post


Link to post
Share on other sites

Posted

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?

Share this post


Link to post
Share on other sites

Posted

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.

1 person likes this

Share this post


Link to post
Share on other sites

Posted

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

2 people like this

Share this post


Link to post
Share on other sites

Posted

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 

Share this post


Link to post
Share on other sites

Posted

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.

2 people like this

Share this post


Link to post
Share on other sites

Posted

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
1 person likes this

Share this post


Link to post
Share on other sites

Posted

@Asik

 

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

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted

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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.