Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

recursion and memoization to find a pell number

 
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator



Hey guys, i wrote this program for an interview process

The code above gives an exception(NullPointerException I believe) for inputs above 4000.it was required to use a technique called memoization along with recursion to implement this problem. I think that i have done the memoization part correctly. but the program fails if given a value greater than 4100 sometimes more than 4200(the program sometimes works for values up to 4500 too). can anybody please tell me what is going on here.

heres the question:

In this question, you are required to write a program which generates a nth Pell number using Recursion and Memoization.
A Pell number (nth Pell number is represented as P(n)) is recursively de fined as:
Pn = 0 if n = 0;1 if n = 1;2*P(n-1) + P(n-2) otherwise.
The above function when expanded, gives rise to the series: 0,1,2,5,12,29,70,169,
408 ... The zeroth Pell number P(0) is 0, rst Pell number P(1) is 1, sixth Pell
number P(6) is 70 etc.
To finnd nth Pell number using a computer program, one of the technique used is recursive generation. But using recursion alone is not an efficient way
to generate a Pell number .To calculate P(4), P(3) and P(2) is computed. To calculate P(3), P(2) and P(1) is computed. But as you observe, P(2) is computed again. This is a repeated computation. This repeated computation is avoided by storing already computed P(k) value in a data structure and using that value to compute other Pell numbers. This technique is called Memoization. Your task is to write a program to generate P(n) using Recursion and Memoization. Your program should compute l Pell numbers for which the input and output format is as follows:
 The first line will contain l cases.
 The next l lines will have the value of n in each line for which P(n) has to be computed. For your program, 10 <= n <= 10000
 The output should output a P(n) for each n in a new line.

 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Where does the exception happen? What's the stack trace? Did you try finding out why you got that exception?
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried e.printStackTrace()
this message gets printed out a large numbere of times..at PellFinal.pell(PellFinal.java:105)
e.getMessage() returns null. so i dont know what type of exception is being caught..im pretty new new to exception handling.
at PellFinal.pell(PellFinal.java:105)
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

thejwal pavithran wrote:Hey guys, i wrote this program for an interview process...


Thejwal,

Please don't put excessively long lines inside code blocks. It makes your thread hard to read. I've broken them up for you this time, but please re-read the UseCodeTags page thoroughly.

Thanks.

Winston
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Its a StackOverflowError. I just found out how to make use of System.out.println(e) to get the type of the error..i think that this is not an infinite call because the same program gives output for smaller values..any ideas please?
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

thejwal pavithran wrote:Hey guys, i wrote this program for an interview process...


Thejwal,

Please don't put excessively long lines inside code blocks. It makes your thread hard to read. I've broken them up for you this time, but please re-read the UseCodeTags page thoroughly.

Thanks.

Winston



okay
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator



Can the above function result in infinite recursive calls? I get correct output for values less than 4000. but after that i get a StackOverFlowError.
can anybody help me?
 
Jesper de Jong
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To get a StackOverflowError you don't necessarily have to have an infinite number of recursive calls. The size of the stack is limited (to a few MB per thread - I don't know what the default size is, it depends on your exact Java version and operating system). If recursion goes too deep, you'll get a StackOverflowError.

I haven't tried to analyze your code, but it could very well be that for large inputs the number of nested calls becomes so great that the stack overflows.

You can set the stack size with the -Xss switch when you run your application. Ofcourse that won't solve the problem, it would just set the limit higher.

If you really want to eliminate the risk of a StackOverflowError, you'll have to rewrite your method so that it uses a regular loop instead of recursion.
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
so basically there is nothing wrong with the code right? i was under the assumption that the error was due to bad coding. i couldnt seek help earlier regarding this as it was part of an interview process..I hope the reviewers don't reject the code.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

thejwal pavithran wrote:Can the above function result in infinite recursive calls? I get correct output for values less than 4000. but after that i get a StackOverFlowError.


Well, from the look of it, that would result in 4,000 recursive calls, which is definitely too much. Recursion is usually used with "divide and conquer" algorithms that reduce the number of calls logarithmically. Using it for linear algorithms (Fibonnaci sequences are a common bad example used to illustrate recursion) is generally a bad idea.

Also, from what I can gather from Wiki (never heard of 'em before), Pell numbers increase exponentially; so it's quite possible that the 4000th Pell number either
(a) Won't fit in a BigInteger.
(b) Will take so long to calculate that you'll die waiting.

Winston
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay good to hear again that the question is what needs to be changed..i noticed just now..I forgot to add a package name would a name clash really irritate reviewers? any code reviewers out here?
 
lowercase baba
Posts: 13013
66
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

thejwal pavithran wrote:so basically there is nothing wrong with the code right?


I don't think anybody is saying there is nothing wrong with the code.

What they are saying is that you don't necessarily have an infinite number of recursive calls just because you get a stack overflow. You may have an infinite number of calls, or you may not. You may have some other error - your computation may be wrong, you may have a spelling typo, there may be other errors. Most people here aren't going to take the time to do any DEEP analysis of your code.


Looking at your code for about 10 seconds, my biggest criticism is that there aren't any comments - nothing to explain what the code is doing or how it works.

Next, "tm" is a TERRIBLE variable name. Trademark? Too Much? Ted Might? Tickle Me? What the heck does "tm" mean? Variable names should be descriptive, not cryptic. I'm guessing it stands for "Tree Map", but what happens if you need two TreeMaps? would you use tm1 and tm2? I would have a long conversation with anyone on my team who wrote production code with such terrible names.

Sadly, now i look a little more at your code, and I see you actually DID use "sc" and "sc2". this is terrible.

 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

fred rosenberger wrote:

thejwal pavithran wrote:so basically there is nothing wrong with the code right?


I don't think anybody is saying there is nothing wrong with the code.

What they are saying is that you don't necessarily have an infinite number of recursive calls just because you get a stack overflow. You may have an infinite number of calls, or you may not. You may have some other error - your computation may be wrong, you may have a spelling typo, there may be other errors. Most people here aren't going to take the time to do any DEEP analysis of your code.


Looking at your code for about 10 seconds, my biggest criticism is that there aren't any comments - nothing to explain what the code is doing or how it works.

Next, "tm" is a TERRIBLE variable name. Trademark? Too Much? Ted Might? Tickle Me? What the heck does "tm" mean? Variable names should be descriptive, not cryptic. I'm guessing it stands for "Tree Map", but what happens if you need two TreeMaps? would you use tm1 and tm2? I would have a long conversation with anyone on my team who wrote production code with such terrible names.

Sadly, now i look a little more at your code, and I see you actually DID use "sc" and "sc2". this is terrible.



I am still trying to get the hang of java or to be really frank programming..Thanks for pointing out the smaller things I can pay attention to..To be honest all I had in mind was to get a program that printed the correct outputs before the tight deadline..
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:...[pell(4000)] Won't fit in a BigInteger...


Looks like I was wrong about that; however, the final result will have more than 1500 decimal digits and you'll have to go through 4,000 iterations to get to it; so, even assuming you can set your stack space big enough, you're likely to wait quite a while.

Winston
 
fred rosenberger
lowercase baba
Posts: 13013
66
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

thejwal pavithran wrote:I am still trying to get the hang of java or to be really frank programming..Thanks for pointing out the smaller things I can pay attention to..To be honest all I had in mind was to get a program that printed the correct outputs before the tight deadline..


My PERSONAL opinion, if I had given out this assignment to job candidates, is that I would prefer clean, neat, well documented code that doesn't work over poorly written code that does work.

Studies I've see say that for any given piece of code, you spend much more time debugging/fixing code than actually writing it in the first place. That makes the internal documentation super-critical. Writing comments and using good variable names is something you should start doing NOW, on every piece of code.

I will often write comments before I write code. if nothing else, a brief statement of what the code is supposed to do at a very high level.

Having said that, OVER-commenting is just as bad. I've seen things like this, and think they are terrible, too:


comments like those add nothing, and actually make it harder to read.
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
(a) Won't fit in a BigInteger.



My understanding is that BI itself doesn't impose any size limits, and numbers can grow arbitrarily large, subject only to the limit of your available memory and how long you're willing to wait for an answer. Or is there some inherent hard upper limit, like no more than Integer.MAX_VALUE digits or something?
 
Marshal
Posts: 74359
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There probably is an upper limit to the size of BI, but the documentation keeps quiet about it. They will probably not represent Graham’s number accurately.
 
Master Rancher
Posts: 4055
56
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:My understanding is that BI itself doesn't impose any size limits, and numbers can grow arbitrarily large, subject only to the limit of your available memory and how long you're willing to wait for an answer. Or is there some inherent hard upper limit, like no more than Integer.MAX_VALUE digits or something?


The magnitude needs to fit in an int[], which can have a max of Integer.MAX_VALUE elements. So the upper limit from that is ((2^32)^(2^31-1)) - 1. You'd need 2 GB of memory to achieve this.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:The magnitude needs to fit in an int[], which can have a max of Integer.MAX_VALUE elements. So the upper limit from that is ((2^32)^(2^31-1)) - 1. You'd need 2 GB of memory to achieve this.


And actually, that's compromised by the fact that bitLength() returns an int (something I've sent in bug fixes about twice; but no reply as yet) and bitwise methods take an int index, so I suspect that the practical limit is a magnitude < 2^Integer.MAX_VALUE (the sign is held separately).

Still pretty darn big though.

Winston
 
Mike Simmons
Master Rancher
Posts: 4055
56
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes. Though I believe a larger BigInteger would work fine in other respects, its bitLength() method would yield incorrect results.
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So is there any precaution that can be taken(apart from the compilation option to increase stack size) in the code to prevent the stackOverFlow error?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

thejwal pavithran wrote:So is there any precaution that can be taken(apart from the compilation option to increase stack size) in the code to prevent the stackOverFlow error?



Other than increasing stack size, your only option is to use less stack. There are some general things you can do toward that end. I don't know how well they'll apply to your specific situation.

1. Make sure your recursion actually ends eventually. Most current hardware does not support infinite stacks.

2. Push less on the stack each call. By reducing the number of parameters and local variables, you reduce the amount of stack each recursive call uses.

3. Reduce the number of recursive calls by doing the work of multiple recursive calls in a single invocation. Note that this may require additional local variables though, so you'll have to balance this against #2.

4. Break the problem into multiple iterative steps at the large-scale level. That is, as an example, instead of making one recursive call that goes 10,000 levels deep, make 100 calls that each go 100 levels deep.
 
Marshal
Posts: 26910
82
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Seems to me that if you use enough memoization, as described in your requirements, it wouldn't be necessary to use recursion at all. But the requirements say to use recursion anyway -- I can't figure out why they would say that.
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:Seems to me that if you use enough memoization, as described in your requirements, it wouldn't be necessary to use recursion at all. But the requirements say to use recursion anyway -- I can't figure out why they would say that.



I guess they wanna see how effectively candidates will avoid a stackOverflowError
 
sinatra roger
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:So is there any precaution that can be taken(apart from the compilation option to increase stack size) in the code to prevent the stackOverFlow error?




Other than increasing stack size, your only option is to use less stack. There are some general things you can do toward that end. I don't know how well they'll apply to your specific situation.

1. Make sure your recursion actually ends eventually. Most current hardware does not support infinite stacks.


yeah i have included a base condition.

This point below ill keep in mind and try to do something like : If the input is more than 3900, instead of passing this directly, i will try to break up
the input into several pieces and then invoke the functions.


4. Break the problem into multiple iterative steps at the large-scale level. That is, as an example, instead of making one recursive call that goes 10,000 levels deep, make 100 calls that each go 100 levels deep.

 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic