• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursive methods inside recursive method  RSS feed

 
Brian Kenney
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion explanation...I cannot wrap my head around the explanation. Can someone please help? I know the answer is 16, I just don't know why. I understand if it is only one recurusive call, but two? HELP!

import java.util.*;
import acm.program.*;

public class Recursion extends ConsoleProgram{

public int recur(int n)
{
if (n<=10)
return n * 2;
else
return recur(recur(n / 3));
}

public void run(){

println(recur(27));

}
}
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Adjust as needed until you can follow the steps.
 
Anayonkar Shivalkar
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Brian Kenney,

Welcome to CodeRanch!

Jeff Verdegan has already explained with a code, however, just wanted to mention that recursion itself means that when a method is called inside same method. It's just either method inside same method, or recursive method (not recursive method inside recursive method).

If you run code made by Jeff Verdegan, and try to debug it (with IDE or paper-pencil), you'll get it.

I hope this helps.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Verdegan wrote:Adjust as needed until you can follow the steps.

<qotd>
To understand recursion, you must first understand recursion.
</qotd>

Winston
 
Brian Kenney
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok...I get how the result is 16. So, how do you know how many times it executes?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian Kenney wrote:ok...I get how the result is 16. So, how do you know how many times it executes?


I don't. And it's not necessarily easy to predict. Certainly this one would take me a while to figure out. Others, like factorial, are simple to predict (although easy to get a fencepost error).
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
actually it is really quite easy (now don't think that i am saying is it obvious until you grok it,
but it is easy).

first: remember the first rule of recursive functions:
there is a test for the trivial case,
then there is a call back to the function.

second: it is far easier if you map out the calls with specific values.

Lets map out your code shall we:

recure(27)
..return recure(recure(27/3))
..return recure(recure(9))
..return recure(18)
..return recure(recure(6))
..return recure(12)
..return recure(recure(12/3))
..return recure(recure(4))
..return recure(8)
..return 16

run through the logic and follow the code.

at some point you will get the aha moment where this is obvious. It is really quite simple, but
it is often very, very hard to grasp. My only suggestion is to map out calls like i did above. sometime
it will snap and seem obvious. Until then, just keep trying.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Fahlbusch wrote:actually it is really quite easy


Apparently we have different definitions of "easy." For me, determining the number of times a method will recurse is easy IFF I can do it for the general case with a glance at the code. If I have to spend a minute or two mapping out a specific case with pencil and paper, that ain't easy.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff,

i'm sorry but this function is (at least to me) is trivial. I recommended to the OP that he maps the function (method) just as i do to my students. I was not commenting on your very good reply.

But then again, i have had many, many years looking at such code and recursion should never be taken lightly. but once you get the hang of it it is quite simple.

And yes i didn't need to map it out to see the depth, but i work with recursion often.

Be well

-steve
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Fahlbusch wrote:Jeff,

i'm sorry but this function is (at least to me) is trivial. I recommended to the OP that he maps the function (method) just as i do to my students. I was not commenting on your very good reply.


To each his own. I'm not offended in the least. :-)

And I'm not at all suggesting that the OP shouldn't map out the calls as you have described. I think it's a good exercise.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Fahlbusch wrote:I recommended to the OP that he maps the function (method) just as i do to my students.

I am unfamiliar with this terminology. What does it mean to map a function/method?
 
Jayesh A Lalwani
Rancher
Posts: 2762
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, you definitively need to map out recursion functions before you get to a point where you can just see a function and tell how many times it will be called. Our brains are not wired from birth to handle recursion. Although, they can be. It needs a lot of practice before your brain can automize that

It's just like when little kids learn to add. As adults, we can see 2 + 3 and know 2 + 3 = 5. We don;t need to count on our fingers (hopefully not none of us in the forum atleast). However little kids need to start counting on their hands before they automize the answer. We aren't born knowing 2 + 3 = 5. It's something that our brain ultimately wires itself to do by constant repetition

Recursion is the same thing, expect taken to the larger degree. You need to map out the functions by hand only one thousand times before you start automizing the thought process.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jayesh A Lalwani wrote:Although, they can be. It needs a lot of practice before your brain can automize that...

I guess so. I've been programming for more than 30 years, and I still find anything more than "trivial" a pain (kind of like reflection code ).

That said, I have written several parsers in my day; and I do enjoy finding a "beautiful" recursive solution.

Winston
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dennis Deems wrote:I am unfamiliar with this terminology. What does it mean to map a function/method?

see this, from Steve's post on Friday:


Lets map out your code shall we:

recure(27)
..return recure(recure(27/3))
..return recure(recure(9))
..return recure(18)
..return recure(recure(6))
..return recure(12)
..return recure(recure(12/3))
..return recure(recure(4))
..return recure(8)
..return 16


It basically means "Do it by hand on paper".
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:
Dennis Deems wrote:I am unfamiliar with this terminology. What does it mean to map a function/method?

see this, from Steve's post on Friday:


Lets map out your code shall we:

recure(27)
..return recure(recure(27/3))
..return recure(recure(9))
..return recure(18)
..return recure(recure(6))
..return recure(12)
..return recure(recure(12/3))
..return recure(recure(4))
..return recure(8)
..return 16


It basically means "Do it by hand on paper".


And whether doing it by hand on paper or by looking at the output from println() calls, one thing that can help is to have the number of leading dots indicate the current level of recursion.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!