Reversion: It may be amazing that a method can call itself, but why shouldn't it be able to? A method call is a transfer of control to the start of the method. This transfer of control can take place from within the method as well as from outside.
All this may seem like passing the bulk. Someone tells me to find the 9th triangular number. I know this is 9 plus the 8th triangular number, so I called Martin and ask him to find 8th number.When I hear back from him, I'll add 9 to whatever he tells me and that will be the answer. Martin will ask 7th number from other person. This process continues with each person passing the buck to another one. Where does this buck-passing end? Someone at some point must be able to figure out an answer that doesn't involve asking another person to help them.
The Characteristics of Recursive methods:
. it calls itself
. when it calls itself, it does so to solve a smaller problem. In each successive call of a recursive method to itself, the argument becomes smaller(or perhaps a range described by multiple arguments becomes smaller), reflecting the fact that the problem has become "smaller" or easier.
. There's some version of the problem that is simple enough that the routine can solve it, and return, without calling itself.
Is recursion Efficient? Calling a method involves certain overhead. control must be transferred from the location of the call to the beginning of the method. In addition, the arguments to the method, and the address to which the method should return, must be pushed onto an internal stack so that the method can access the argument values and know where to return.
Towers of Hanoi algorithm:
1. move the subtree consisting of the top n-1 disks from S(source Tower) to I(Intermediate tower)
2. Move the remaining (largest) disk from S to D(Destination Tower)
3.Move the subtree from I to D
public static void doTowers(int topN, char from, char inter, char to){
if(topN ==1)
log.info("Disk 1 from " + from + " to " + to);
else{
doTowers(topN-1,from,to,inter); // from --> inter
log.info("Disk " + topN + "from " + from + " to " + to);
doTowers(topN-1,inter,from,to);
}
}
All this may seem like passing the bulk. Someone tells me to find the 9th triangular number. I know this is 9 plus the 8th triangular number, so I called Martin and ask him to find 8th number.When I hear back from him, I'll add 9 to whatever he tells me and that will be the answer. Martin will ask 7th number from other person. This process continues with each person passing the buck to another one. Where does this buck-passing end? Someone at some point must be able to figure out an answer that doesn't involve asking another person to help them.
The Characteristics of Recursive methods:
. it calls itself
. when it calls itself, it does so to solve a smaller problem. In each successive call of a recursive method to itself, the argument becomes smaller(or perhaps a range described by multiple arguments becomes smaller), reflecting the fact that the problem has become "smaller" or easier.
. There's some version of the problem that is simple enough that the routine can solve it, and return, without calling itself.
Is recursion Efficient? Calling a method involves certain overhead. control must be transferred from the location of the call to the beginning of the method. In addition, the arguments to the method, and the address to which the method should return, must be pushed onto an internal stack so that the method can access the argument values and know where to return.
Towers of Hanoi algorithm:
1. move the subtree consisting of the top n-1 disks from S(source Tower) to I(Intermediate tower)
2. Move the remaining (largest) disk from S to D(Destination Tower)
3.Move the subtree from I to D
public static void doTowers(int topN, char from, char inter, char to){
if(topN ==1)
log.info("Disk 1 from " + from + " to " + to);
else{
doTowers(topN-1,from,to,inter); // from --> inter
log.info("Disk " + topN + "from " + from + " to " + to);
doTowers(topN-1,inter,from,to);
}
}
Comments
Post a Comment