• Post Reply Bookmark Topic Watch Topic
  • New Topic

I have a problem with recursion  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i started learning C a year ago.
then I started java 5 months ago.
i did couple of works in java. for example a code that rotates image, makes it gray, and more...most of the code i used loops . i understood loops very well.
now i'm starting to learn complexity and recursion, stacks and linked lists. i understood most of them all exept recursion.
why I find it hard to understand it ? i saw a factorial code. i understood the implementation . but how it works and what's going behind the scene ?

i know that when i have have a return statement its get out of the method.
so why in recursion i have,lets say, two return statement and its still remains in the method ?
or if i have if else statement. after the if part . it returns 1 and then it goes to the else part and excecute it.. because i know that if the if part is true the else doesnt matter.
for example i have this code that calculates power:




i tried to wrtoe the steps and iterations.
and put System.out.print() between parts of code to try understanding. but still i didnt .
i may not be correct but the steps i think i understood and not in 100 % are:
- the base case is when n is 0
-there's a call to power when n/2
- when n is 0 its returns 1 ( why it dont quit the method ? in a regular method if i put return in the middle of the method it will quit it )
- and after . the values are kept on the stack right ? the kept on the stack .
.. i need to understand the steps . i really want to be good at it.
 
Tim Cooke
Marshal
Posts: 4051
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done on defining your exit condition, when n == 0. This is the bit that a lot of learners miss and end up with an infinite recursive loop followed shortly after by a StackOverflowError. However, I don't really get what the "n/2" is for in your recursive call.

Naturally we see power calculated this way:

power(k, n), where n is:
0 = 1
1 = k
2 = k * k
3 = k * k * k

But you can also think about it this way:
0 = 1
1 = k * 1
2 = k * k * 1
3 = k * k * k * 1

After which you can see a pattern emerging where the next higher value of n is k times the power of n - 1. So you can define the power function as:
0 = 1
n = k * power(k, n-1)

Now see if you can translate that into Java code.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What you are supposed to do when you have an even exponent is to seek
power(arg * arg, exp / 2)
and for an odd exponent
arg * power(arg, exp - 1) // In this case exp - 1 is even.
That way you are running in logarithmic complexity.
 
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
Dan D'amico wrote:- when n is 0 its returns 1 ( why it dont quit the method ? in a regular method if i put return in the middle of the method it will quit it )

In fact, it does quit the method and returns to the method that calls it. What may confuse you is that the method that calls it is often the same method in recursion. In your case a call to power() adds two values to the stack: k and n. Each call adds two more. Each return pops two off the stack until it finally returns the result to the original caller.
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks.
what really helped me to understand recursion is to understand what happnes in the runtime stack.
just went on this 3 hours
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!