Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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.

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.

posted 2 years ago

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.

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.

Tim Driven Development

Campbell Ritchie

Marshal

Posts: 56600

172

posted 2 years ago

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

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.