This week's book giveaway is in the Kotlin forum.
We're giving away four copies of Kotlin in Action and have Dmitry Jemerov & Svetlana Isakova on-line!
See this thread for details.
Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion  RSS feed

 
mike pa
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all. Noob here. I have to write a program that deals with recursion (not sure if this is a beginner topic). I already did one that takes a string and reverses it. I used a method called Reverse that took the string, got the last char of the string, then called Reverse again with a substring, taking 1 letter off each time. Easy enough.

Now I need to write a program using recursion that will give the nth line of Pascal's triangle. I understand how the triangle works and could probably construct one using a multidimensional array, but am baffled as to how to get it with recursion. I want to call a method named getLine (int n) and somehow recurse that method to give me the result. Any ideas (or code hints) would be awesome. Thank you.
 
Keith Lynn
Ranch Hand
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The best way to approach a problem like this would be to work out how you would do it by hand and then translate that to pseudocode.

In this case, how would you get row n+1 of Pascal's triangle if you know row n?
 
mike pa
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hmm.. I can see what you are saying. I'm somewhat confused though, because again, you would have to know what line n is to get to line n+1. I supposed you could start from row 1 and go down from there, maybe using 2 arrays, 1 to store the line you know and, the other to store the next line you want to compute. I had missed the lecture when the lab was assigned but was under the impression a multidimensional array was not to be used. The professor mentioned only using an array no bigger than size 15 to do this lab, leading me to believe it's supposed to be a 1 dimentional array.
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i dont know about a one dimentional array..
two sounds better..

1
11
121
1331
14641

etc..

well if he told you no bigger than 15, 15 is n...

so you would just call getLine(int n)

util it is >= 15

else return getLine(n+1);

each time you would have the line start with 1 right?

then you would take the first two numbers in the ith array

and add them to get the second..

and the again until you get to the end, and then add another 1.

then return getLine(n+1).

util you hit the 'base case' aka "n == 15"

then you would have your 2d array with the result being the last
index of that array..

i believe this should be the kinda pseudocode for the assignment...

shouldn't be too bad..

Justin Fox
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you could have a String, which would represent the result..


like:

String result += Integer.toString(answer);

where result was "13", but now is "133".

then the second number would be the nth number of that string before.

and so you would slap a string representaion of the number 1 on the end..

"1331"

so this way you could just use a single array of Strings...

and not have to worry about making the rows of a 2d array big enough..

Justin
 
mike pa
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks. I'll work with this and see what I get.


I know this isn't hard especially after what you gave me but my motivation is not here tonight. I hate school, every day/week something happens to make me hate it more, and after 4 years of college (I have an associates), I'm barely a sophomore at my current school (screwed with credits not transferring). I've lost all desire to work and can't wait to transfer/drop out in the spring. For me, its basically a push to get to December with a C to get my class and time at this school done with. So before you or anyone thinks I'm an idiot or slacker, try to put yourself in my shoes. And if anyone wants to make $5.. oh wait I'm not supposed to say that lol.
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
believe me I know how you feel, maybe not in the associates department,
but I'm taking, survey of programming languages, software engineering,operating systems, (graduate)networks, and Programming fundIV...

I'm perdy loaded down...

dont fret, just keep coding, you'll get it : )

Justin
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!