• Post Reply Bookmark Topic Watch Topic
  • New Topic

there's a way to really understand recursion ?  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i undertsood that a method that calls herself must have a base case that finally the method will terminate.
but for computational part.i dont understand how it works.

for example:


 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Dan,

First of all, I would suggest you do not use loops, otherwise it gets messy and very complicated to understand.
Think about it as, ITERATIVE way and RECURSIVE way ONLY.

This is a part, which actually very difficult to explain.
Try to ask more precise, and we'll try to explain on a real case how it works.

1) My personal suggestion would be, to rewrite sorting (bubble sort, insertion sort) algorithms in recursive way, with no loops at all.
After that, i'm pretty sure you would understand much more.

2) In order to achieve that, find some animated video's how those sorting algorithms works, and then from visual field you could try to build recursion calls.
 
Tony Docherty
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That code does not produce the output shown and in fact doesn't even compile. Apart from the syntax errors the first if statement should be for n <= 0
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In this particular case should be if (n==0) and nothing else.
 
Tony Docherty
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No it should be n <= 0. Think about what would happen if you used n == 0 and someone passed in a negative number.
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This case it's not worth of discussion.
It is a bad example in order to understand recursion.
 
Tony Docherty
Bartender
Posts: 3271
82
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Assuming it is changed to correct code ie:
it works as follows:

The main method calls recursionMethod(4)
The recursionMethod method runs with n = 4
n is greater than 0 so the return is ignored
The recursionMethod is called with n-1
The recursionMethod method runs with n = 3
n is greater than 0 so the return is ignored
The recursionMethod is called with n-1
The recursionMethod method runs with n = 2
n is greater than 0 so the return is ignored
The recursionMethod is called with n-1
The recursionMethod method runs with n = 1
n is greater than 0 so the return is ignored
The recursionMethod is called with n-1
The recursionMethod method runs with n = 0
n is equal to 0 so the method returns
The calling method now continues (where n = 1)
The for loop to print A runs n times (ie 1 time)
The for loop to print B runs n times (ie 1 time)
A new line is printed
The method returns
The calling method now continues (where n = 2)
The for loop to print A runs n times (ie 2 times)
The for loop to print B runs n times (ie 2 times)
A new line is printed
The method returns
The calling method now continues (where n = 3)
The for loop to print A runs n times (ie 3 times)
The for loop to print B runs n times (ie 3 times)
A new line is printed
The method returns
The calling method now continues (where n = 4)
The for loop to print A runs n times (ie 4 times)
The for loop to print B runs n times (ie 4 times)
A new line is printed
The method returns
The calling method (ie the main method) now continues
The program terminates

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tony Docherty wrote:
The recursionMethod method runs with n = 0
n is equal to 0 so the method returns
The calling method now continues (where n = 1)
....
....
the program retimantes.


i understood all except the first line in the quote and so on...
besides that i understood what has been written before the quote
- can you explain please the above ?
- also what does it mean "the program returns" - if the return statement doesnt have a value.
- and why after n is 0 n become 1 , there's no increment in the code..

actually i did 4 big assignments in this 2 months got grades with avarage of 98)
recursion is my only problem. i understood how recursion works for example for calculating factorial. but this is somethinge else
and ofcourse i just want to understand and not looking for a solution.
and yes my mistake i should have written n<=0
 
Tony Docherty
Bartender
Posts: 3271
82
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not sure what you don't understand about the bit you quoted.

The part above the quoted line is the recursive calls. The method calls itself repeatedly each time passing in a value 1 less than the value it has been given so eventually a call is made with the value '0'. When this happens the execution path through the code changes because the if statement at the beginning of the method becomes true and so the if statement's code block runs ie return; is executed.

Whenever a method returns normally the execution continues at the line after the line that originally called the method. In this case it means execution will continue at line 6. Now what you have to remember is that when a method calls another method (including itself) the current values of all its local variables are saved (which in this case is the value in variable 'n') and when the called method returns the state of those variables are restored. Put in very simplistic terms every time recursionMethod calls itself the value of 'n' is pushed onto a stack and every time recursionMethod returns the previous value of n is popped off the stack until there are no more stored values ie the recursion has totally unwound. So we push onto the stack 4 then 3 then 2 then 1 then the recursive calls end and we pop off the stack 1 then 2 then 3 then 4.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd remove your 'A' and 'B' loops and replace it with some debugging prints, like so...


Output:
N entering = 4
N entering = 3
N entering = 2
N entering = 1
N entering = 0
Returning
N leaving = 1
N leaving = 2
N leaving = 3
N leaving = 4
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tony Docherty wrote:I'm not sure what you don't understand about the bit you quoted.

The part above the quoted line is the recursive calls. The method calls itself repeatedly each time passing in a value 1 less than the value it has been given so eventually a call is made with the value '0'. When this happens the execution path through the code changes because the if statement at the beginning of the method becomes true and so the if statement's code block runs ie return; is executed.

Whenever a method returns normally the execution continues at the line after the line that originally called the method. In this case it means execution will continue at line 6. Now what you have to remember is that when a method calls another method (including itself) the current values of all its local variables are saved (which in this case is the value in variable 'n') and when the called method returns the state of those variables are restored. Put in very simplistic terms every time recursionMethod calls itself the value of 'n' is pushed onto a stack and every time recursionMethod returns the previous value of n is popped off the stack until there are no more stored values ie the recursion has totally unwound. So we push onto the stack 4 then 3 then 2 then 1 then the recursive calls end and we pop off the stack 1 then 2 then 3 then 4.

thanks a lot !, i understood , the explanation of the stack and how it works really helped me with this.
so its turns out that the control is returned with the opposite direction ? i'm guessing this is one form of recursion. this is tail recursion ?



 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Although you can certainly use recursion to replace loops, loops are more often a better choice. My favorite example of recursion is walking a directory tree, that is something that is very difficult to do with loops, and recursion is an ideal choice.
import java.io.File;

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
this is advanced material for me but if i got it right .
you goes through a file and while its not empty you get the contents inside ?
or list of files into the directory.
im guessing .

by the way i liked your example with the N etering and N leaving
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To understand head/tail recursion you might try this.

output:
TAIL RECURSION
N = 1
N = 2
N = 3
N = 4
HEAD RECURSION
N = 4
N = 3
N = 2
N = 1
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan D'amico wrote:
so its turns out that the control is returned with the opposite direction ? i'm guessing this is one form of recursion. this is tail recursion ?


Tail recursion is when each recursive call makes, at most, one recursive call. And that recursive call is at the end of the current call.

Tail recursion is the standard technique to replace a loop with recursion. And of course, your example is *not* a tail recursive call, as you are doing the recursive call in the beginning of the call.

Henry
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
Tail recursion is when each recursive call makes, at most, one recursive call. And that recursive call is at the end of the current call.

Tail recursion is the standard technique to replace a loop with recursion. And of course, your example is *not* a tail recursive call, as you are doing the recursive call in the beginning of the call.

Henry

My bad. Wrote it backwards. (speed!=quality)
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes. understood.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan,

To really understand recursive functions i suggest that you code a binary tree and three functions (methods).... printPrefix, printInfix and printPostfix (you can google for the definitions).

If you understand these methods, you should be good on most recursive functions.

-steve
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!