Understanding Recursion (in Java)?

Question

Understanding Recursion (in Java)?

Answer 1

public int count8(int n) {

if (n == 0) {

return n;

}

if( n % 10 == 8){

int count = 1;

int temp = n / 10;

if( temp % 10 == 8){

count = 2;

}

return count + count8(n / 10);

}

return 0 + count8(n / 10);

}

Answer 2

Any problem that can be solved recursively can also be solved iteratively. That's a fact.



However, recursion is best used for search functions. Search tree walkers with backtracking come to mind almost immediately.



http://en.wikipedia.org/wiki/Backtracking



The JavaBat example above, well, sucks. It doesn't really explain recursion at all and is far too simple to show why it should be used. In fact, for the counting 8's problem, I would tend to opt for an iterative approach!



Historically, recursion has been taught by having students implement Towers of Hanoi or the n-queens problem.



http://en.wikipedia.org/wiki/Tower_of_Hanoi

http://en.wikipedia.org/wiki/N_queens_problem



Having said that, you can find a LOT of debate regarding "Recursion vs Iteration". Here's but a few:



http://math.scu.edu/~dsmolars/ma60/notesa3.html

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

http://www.dreamincode.net/forums/showtopic13188.htm

Answer 3

public static int count(int number) {

if (number == 0)

return 0;



int c = 0;

if (number % 100 == 88)

c = 2;

else if (number % 10 == 8)

c = 1;

return (c + count(number / 10));

}



The key to understanding recursion is to not think too hard. I couldn't understand the concept myself until I realized - recursion just works, period!



All you need to do is to find out, how the problem can be solved by solving the same problem but with smaller input.



First of all, note how I started the algorithm. I checked to see if the number is 0. If it is, that means that previous number was 1 digit long. That means, I must stop recursively calling algorithms. So I just returned a zero.



That's how you should always start your recursive algorithms. Check for the terminating condition.



I have declared a variable 'c'. It will store a numeric count for the rightmost number.



Then I started dividing a problem into a smaller, similar problem. First, I checked the last 2 digits. If those digits are 88, that means that the number has two 8's together. So the numeric value for the rightmost digit is 2.



If previous test failed, I check to see if there's just one 8. If there is, the numeric value for it will be 1.



If not, the numeric value gets to stay at 0.



That's it! I have examined the rightmost digit. Now, all I have to do is make the problem smaller. I delete the rightmost digit, and pass the rest of the number to the same function, which will examine the rest of rightmost digits. That function will return the numeric values for the rest of numbers, I will add that number to my and will return the total.