Win a copy of Rust Web Development this week in the Other Languages 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
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

Recursive Function to Solve

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey Folks!

Really excited to find this and create an account. I just finished my last sequence of a three term OOP sequence at a university in the United States. Very excited and I like Java. I had a problem on my last final. Wish I could remember exactly how I solved it. But it was a recursive function to solve the following problem:

Here was the problem. I'll try to be concise as possible.

Assume a class will have two integer variables, a  and b. Write a method that takes an integer, n, and returns the value of ab in in the sequence. For example, if a = 3, and b = 4 the sequence would be calculated as a b ab ab^2 a^2b^3 a^3b^4, etc., etc. So in this example, when a = 3 and b = 4 you would get:

3 4 12 48 144

So if you had a function



and you threw the method 3 it would return 48.

I think I wrote something like this:


I know this is not right. Can anyone help me out with this? It looks like a fibbinacci thing, but I'm not sure. Thank you!

-Steve
 
Marshal
Posts: 74654
335
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

That isn't a function. A function takes an input and returns an output, so it can't have void instead of a return type. Ideally, it should also always give the same output for the same input, and have no side‑effects.
What you have looks rather like the naïve version of a recursive Fibonacci function, but beware: each call creates two calls, so that technique will rapidly expand and will run in exponential complexity.
That is a bit unusual for a recursive method. A recursive method usually starts with a large value, which you don't appear to have, and goes smaller. I am therefore worried that your method is going from small to large and may never reach the base case and go on for ever until it exhausts the available memory or stack space.
A recursive method also has to include a base case, which terminates it. You appear to have two base cases, but that's all right. Also a recursive method usually returns a value which goes back to the previous call. I would suggest you start with factorials, remembering that the argument is a non‑negative integer (a member of the natural numbers set) and that 0! is defined as 1. That means you can use 0 as the base case. If you try anything bigger than 12! you will get an overflow error with ints; I think longs can accommodate up to 21!.
Once you have factorials working (much easier to envisage), come back to the current problem, but first work out a formula for going from element to element  ₁. I am afraid I don't think that will be easy.
 
Sheriff
Posts: 26951
83
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you want an interesting recursive function you might want to have a look at the Ackermann function. (Okay, Wilhelm didn't spell his name quite right but have a look anyway)
 
Campbell Ritchie
Marshal
Posts: 74654
335
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ackermann is too scary for “Beginning”. When you are feeling very brave or very drunk, watch this Computerphile video about Ackermann's numbers. Maybe this Compterphile video will be less scary.
 
Campbell Ritchie
Marshal
Posts: 74654
335
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Maybe 15 minutes ago, I wrote:. . . . Maybe this Compterphile video will be less scary.

It was indeed less scary. But there are two things I would do differently:-
  • 1: Use 0 as the base case.
  • 2: Use the ?: operator, which is also available in C.
  • So some C code might look like this:-I shall leave it to you to convert that to Java® code.
     
    Marshal
    Posts: 8198
    585
    Mac OS X VI Editor BSD Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    “...and this is where the headache starts to set in” - great videos, watching again.
     
    Steven Ackerman
    Greenhorn
    Posts: 6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    It looks like the above C code is for computing factorials. I am not trying to do that. Here is java code for that. It looks like it is computing n! = n × (n−1)! So, Java:


    I am not trying to do that. I am trying to let's say that this is a set: {a, b, ab, ab^2, a^2b^2, a^2b^3}, where a and b are integers. For an example if a = 3 and b=4 if I grabbed the third integer from the set it would be 12, because a*b equals 12. So I was trying to right a method that computed what the number is at a certain place, n. So my attempt, was approximately this:



    This is a difficult problem for me to solve recursively. Maybe I could do it in a while loop first and try to turn that into a recursive method. Those were awesome videos BTW. Recursion is pretty cool. Takes some deep thinking. Thanks for all the responses! Happy coding.
     
    Steven Ackerman
    Greenhorn
    Posts: 6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I better clarify. In my desired function, when you put in 3 for in, it should return 12.

    Also, I didn't originally notice how many posts most of you have here. I really appreciate taking the time to look at my post and respond. It's really awesome to have people look that have that kind of experience. I suppose you have seen it all here!

    -Steve
     
    Campbell Ritchie
    Marshal
    Posts: 74654
    335
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Steven Ackerman wrote:. . . . I suppose you have seen it all here!

    -Steve

    Quite a lot of it, but that series is new to me. I don't believe you can solve it until you work out a formula for going from (at least) the 2nd element to those following. Also you need some way to stop the calculation before it overflows the memory or stack space available. The stack space usually goes first.
    I challenge you to work out under which circumstances you will eventually have your output show 0.
    I suggested factorials because they are easier to envisage than your series; the formula is simpler: as you said, n × (n − 1)! Also, that recursion converges on 0, which is a good base case.

    Formatting thing when posting: Don't use ^: write &#x2070, &#xb9, &#xb2, &b3, &#x2074...&#x2079 (inclusive). I think I have got the numbers right. You can use 00b9 (etc) instead of b9.
     
    Steven Ackerman
    Greenhorn
    Posts: 6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:

    Steven Ackerman wrote:. . . . I suppose you have seen it all here!

    -Steve

    Quite a lot of it, but that series is new to me. I don't believe you can solve it until you work out a formula for going from (at least) the 2nd element to those following. Also you need some way to stop the calculation before it overflows the memory or stack space available. The stack space usually goes first.
    I challenge you to work out under which circumstances you will eventually have your output show 0.
    I suggested factorials because they are easier to envisage than your series; the formula is simpler: as you said, n × (n − 1)! Also, that recursion converges on 0, which is a good base case.


     
    Steven Ackerman
    Greenhorn
    Posts: 6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Sorry for all the strange formatting and submitting extra stuff. Thanks for the above suggestion. I was working on this all morning. I finally decided to work it through without recursion and try to successfully calculate it with a while statement. I only got to work for n <=3. It was still progress. What I noticed is that it looked much like the Fibonacci sequence only with multiplication. So I tried the recursive solution with the results being multiplied. Wrong answer! I reversed them and got it works. Here's the code for anyone else pounding their head against the wall like I was. Wish I would have thought of this on the test. It was an awesome question. I learned a lot from it. I should have known the solution was something much simpler than I had first thought.

     
    Campbell Ritchie
    Marshal
    Posts: 74654
    335
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Yes, that looks a nice recursive calculation. Well done.

    As I told you earlier, you are going to go into exponential complexity like that. Also, if you look in the old Sun style guide, you will find you can greatly simplify that formula with the ?: operator. You can reduce the whole method to one statement.
     
    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