Jump to content



Photo

Recursion

Answered Go to the full post java

  • Please log in to reply
11 replies to this topic

#1 The Teej

The Teej

    Also known as The Tjalian

  • Joined: 03-October 05
  • Location: England, UK

Posted 31 July 2013 - 13:07

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


Best Answer Andre S. , 31 July 2013 - 21:39

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.

Go to the full post



#2 BGM

BGM

    Wibble Wobble™

  • Joined: 30-March 03
  • Location: Farnborough, UK

Posted 31 July 2013 - 13:13

is there a question here ? :D



#3 firey

firey

    F͎̗͉͎͈͑͡ȉ͎̣̐́ṙ͖̺͕͙̓̌è̤̞͉̟̲͇̍̍̾̓ͥͅy͓̍̎̌̏̒

  • Tech Issues Solved: 6
  • Joined: 30-October 05
  • Location: Ontario, Canada
  • OS: Windows 7
  • Phone: Android (4.1.2)

Posted 31 July 2013 - 13:18

 

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

 



#4 OP The Teej

The Teej

    Also known as The Tjalian

  • Joined: 03-October 05
  • Location: England, UK

Posted 31 July 2013 - 13:25

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?



#5 firey

firey

    F͎̗͉͎͈͑͡ȉ͎̣̐́ṙ͖̺͕͙̓̌è̤̞͉̟̲͇̍̍̾̓ͥͅy͓̍̎̌̏̒

  • Tech Issues Solved: 6
  • Joined: 30-October 05
  • Location: Ontario, Canada
  • OS: Windows 7
  • Phone: Android (4.1.2)

Posted 31 July 2013 - 13:34

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.



#6 kyosuken

kyosuken

    Old Geezer

  • Joined: 27-October 01

Posted 31 July 2013 - 13:38

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



#7 OP The Teej

The Teej

    Also known as The Tjalian

  • Joined: 03-October 05
  • Location: England, UK

Posted 31 July 2013 - 13:42

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 



#8 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 10
  • Joined: 26-October 05

Posted 31 July 2013 - 21:39   Best Answer

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.



#9 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 10
  • Joined: 26-October 05

Posted 01 August 2013 - 02:53

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


#10 kyosuken

kyosuken

    Old Geezer

  • Joined: 27-October 01

Posted 01 August 2013 - 13:16

@Asik

 

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



#11 Garnet H.

Garnet H.

    astropheed

  • Tech Issues Solved: 2
  • Joined: 08-December 11
  • Location: Sydney, AU

Posted 01 August 2013 - 21:25

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



#12 OP The Teej

The Teej

    Also known as The Tjalian

  • Joined: 03-October 05
  • Location: England, UK

Posted 06 August 2013 - 14:02

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!





Click here to login or here to register to remove this ad, it's free!