File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes help in solving recursive problems?? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "help in solving recursive problems??" Watch "help in solving recursive problems??" New topic
Author

help in solving recursive problems??

johny doe
Ranch Hand

Joined: Dec 07, 2007
Posts: 78
how do i build from scrach a recursive function

it seems that i can only try to understand a solved ones

only when i learn some type of recursive function like
2^n
fuction
i can build a similar one
but my big problem that i dont know how to plan it
or build some other type
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 31079
    
163

Johny,
When trying to write a recursive function, think about how you can break up the problem into a smaller piece. This often involves making a number smaller or removing an element from a list. Then think about the "base case" - how do you know when you are done.

And of course practice. It's hard to give general advice. Try an example and post here when you get stuck.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
johny doe
Ranch Hand

Joined: Dec 07, 2007
Posts: 78
my assigment is to build a function called post fix
where wheen i am given a number
the fuction prints
all the combination of numbers that their sum is the given number
for example by the input of number4:
it gives:
4
1 3
2 2
2 1 11 1 1 1
the methods that i need to build are

Public static void partitions (int n)
{
partitions (n, n, "");
}
Public static void partitions (int n, int max, String prefix)
{
}

you told me to build a simpler cases and then to find the rule for every case.
the case that prints only the max number.

Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
}

for the case of max and (max-1) and 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max-1," ",1);

}

for the case of max and (max-2) and 2
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max-2," ",2);

}

for the case of max and (max-2) and 1 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max-2," ",1," " 1);

}

i thought also of these idea
about such loop
but i dont know how to build a recursive function
that each time prints additional member.

for(i=0;i<max;i++){
if (i=0){
System.out.print(max);
}
else
{
System.out.print(max-i," ",i);
}
}//end for
Malayathi Partha Saradhi
Greenhorn

Joined: Nov 30, 2007
Posts: 10
Hello,

Recursive programming is like a stack programming.
so please understand like that so.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 19073
    
  40

how do i build from scrach a recursive function

it seems that i can only try to understand a solved ones

only when i learn some type of recursive function like....


Don't want to rub salt on the wound, but I think that you may have hurt yourself by taking a short-cut to the "solved ones". By going straight to the solution, with previous recursion problems, you understood the specific solution, but didn't really understand how to think recursively.

It may be better to go back and re-do the previous problems. Or at least, don't take a short cut for this one -- as you'll just learn just another specific solution.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
johny doe
Ranch Hand

Joined: Dec 07, 2007
Posts: 78
i was told to try and solve a question
and if i got stuck you will help me go further

thats what i tried to do
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40055
    
  28
Please take it easy. We have all been there, done that, and got the tee-shirt. We know what it is like to have programming not work. We also know that being given a solution doesn't help in the long run. That is why there are limits to how much help we can give.

Three features which all recursive functions display:
  • 1: They call themselves.
  • 2: Each call is slightly simpler, maybe using n - 1 rather than n.
  • There is a simplest-of-all case, called the base case where the recursion stops, otherwise it goes on for ever. A base case commonly has 0 or 1 as an argument.
  • Jeanne Boyarsky is right about "smaller pieces." You can use a factorial recursion to calculate factorials; themethod does not "know how to" calculate factorial(9), but it does "know" to take 9 and multiply it by factorial(8).

    The advice given to go back and analyse problems you ahve seen worked out elsewhere is very sound. Go back to factorial(9) (BTW: If you use int arithmetic, you overflow the bounds of the int type somewhere around factorial 12). This is what you would write down.
    Factorial 9
    Factorial 9 is 9 times factorial 8.
    Factorial 8 is 8 times factorial 7.
    Factorial 7 is 7 times factorial 6.
    Factorial 6 is 6 times factorial 5.
    Factorial 5 is 5 times factorial 4.
    Factorial 4 is 4 times factorial 3.
    Factorial 3 is 3 times factorial 2.
    Factorial 2 is 2 times factorial 1.
    Factorial 1 is 1 times factorial 0.
    Factorial 0 is defined as 1.

    There is an alternative version where "factorial 1 equals 1" is the base case; both produce the same result.

    Remember that at this point you have all those calculations half-done kept on a stack. Recursion is often every efficient, but can be expensive on memory, so you use it on PCs with hundreds of MB of RAM, but you don't use it on mobile devices with 64kB of RAM.

    Now the one basic Java book I can think of which has anything about recursion in is Deitel and Deitel; I have the 6th edition where it's page 744. It describes the factorial recursion (which is efficient) and a Fibonacci recursion (the one which is very inefficient), also how you can backtrack with recursion. Find that, or a recursion tutorial on the Net, which you can find in a few seconds with Google, and read it very carefully. Tutorials for other languages, particularly C, C++ and C#, will still help you with Java.
    See how their problems are broken down. Look at the diagrams in Deitel of how Fibonacci is called.

    Get some paper and a pencil and see how you can break down your problem. Are you going to break it from 4 into 1, 3, or 3, 1, or 2, 2, and how do you plan to do that.
    When you have your pencil and paper version, then you can work it back into code. Good luck with it.

    [edit]Added "factorial(9)" a bit before "factorial(8)."[/edit]
    [ December 27, 2007: Message edited by: Campbell Ritchie ]
    johny doe
    Ranch Hand

    Joined: Dec 07, 2007
    Posts: 78
    i solved my problem

    Public static void partitions (int n)
    {
    partitions (n, n, "");
    }
    Public static void partitions (int n, int max, String prefix)
    {
    system.out.println(n);
    for (i=n;i<max;i++)
    {
    system.out.print(1);
    }
    partitions(n-1,max,prefix);
    }

    i dont know how to make a dynamic array from a string
    so each time it adds the char that i am printing here.

    the answer in my text book is:

    Public static void partitions (int n)
    {
    partitions (n, n, "");
    }
    Public static void partitions (int n, int max, String prefix)
    {
    if(n==0)
    {
    System.out.println(prefix);
    }
    else
    {
    for(int i= Math.min(n,max); i>=1, i--)
    {
    partitions (n-i, i, prefix+" "+i);
    }
    }
    }


    i cant undestand the logic behiמd it
    i realy tried to figure it out
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40055
        
      28
    I am afraid you haven't cracked it. I tried it and got a print-out rather like this:
    1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

    So I pushed ctrl-C.

    Please use code tags round code, and use crtl-C/ctrl-V to quote code so we get it with the indentation preserved and don't get little spelling errors like "system."

    I think the problem at the moment is that you lack a base case; you have to put something in which will test whether you have got down to 0 and which will finish the recursion.

    To make a dynamic array from a String: the simplest way is --- don't. Use a StringBuilder object and use the append() methods. You can easily create a StringBuilder from a String and vice versa; the two classes were designed to work together.

    Get something working which terminates. Remember if you start with 4 the output you expect (you told us yourself) is,
    3 1
    2 2
    2 1 1
    1 1 1 1.
    Download an IDE Something I usually warn beginners against. I usually use Eclipse, but I am pretty sure you can do the same on NetBeans.

    On Eclipse:
    File->new->project->give the project a name.
    R-click the project, create a package.
    R-click the package, create a class in it, give it a name and a main method.
    Copy and paste your working partition methods into that class.
    Look at the text for your class, then click on the left of the line numbers until a blue blob (red on NetBeans, I think) appears.
    This blob is a breakpoint.
    Click run->debug, then open the debug perspective.
    The code will run until it reaches the breakpoint. Debug appears at the top left, and variables/breakpoints at the top right. Click the variables tab.
    Above debug there are three icons with arrows, which are
  • Step into. This follows the execution if you go into a method.
  • Step over. This executes the method but omits showing you the workings of the method.
  • Step return. This finishes the present method call and all 2ndary calls and goes back to the previous calling method (I think, not certain).
  • You can use f5 f6 and f7 for step into step over and step return (I think).
  • Whichever method you are in, you can see the values of the variables in the variables field.
  • Go through it line by line, watch how you go from method to method, watch how the variables change as you go.

    If that doesn't help, write out on paper what you think the sequence of method calls is. Rather like what I wrote about factorials earlier.

    Henry Wong is right that you need to get your head round the logic and structure of the recursive programming. Try my suggestions; if they don't work, see if you can find somebody locally who can explain it to you. It is not good news trying to program if you don't understand what you are trying to do.

    Good luck
    CR
    Jeanne Boyarsky
    author & internet detective
    Marshal

    Joined: May 26, 2003
    Posts: 31079
        
    163

    Johny,
    You found a smaller problem:
    partitions(n-1,max,prefix);

    This is called the recursive case and means you are halfway there. There is also the base case. How does the computer know when to stop the recursion? In your example, it doesn't. Hence the infinite recursion that Campbell showed.

    The base case is actually easier to figure out than the recursive step. Try picking a small value for n (say 4) and trace it through. At each call to partitions, think about whether you have the answer or you need another go. When you have the answer, you've found the guard clause.
    Malayathi Partha Saradhi
    Greenhorn

    Joined: Nov 30, 2007
    Posts: 10
    Hello friend,

    EVERYBODY KNOWS LOCAL VARIABLES STORES IN STACK.

    I will give one example:

    class Simple{
    public static void main(String ar[]){
    method(6);
    }
    public static int method(int i){
    if(i==1) return 1;
    return method(i-1)*i
    }
    }
    this is the recurive program of factorial.

    STACK:
    The evaluation of i-1*i,like that,
    method(6-1)*i -> i=6
    method(6-1) calls method() itself.
    so method(5-1) is called i=5;

    then method(4-1) ....so on.
    atlast method(1) is called .In this situation 1 is returned by method(1);

    In situation ,multiplication will be done.
    method(2-1)*i .........
    johny doe
    Ranch Hand

    Joined: Dec 07, 2007
    Posts: 78
    i tried to compose an algorith for this problem:

    for each number number that we are being given (MAX)
    for each step of the way decrease one number buy 1
    and then
    print the result of (number-1) and the (MAX-number)

    in a case of the step where (2 2)
    we make the same step (it also starts with 2)
    but in this time we split the second 2 to the numbers (1,1)

    i think that we need to do a recursion for this nubmber
    and add its result to the number 2

    but i dont have the imagination of how to accomplish that

    but i think that this is the base case
    to split the number 2 into 1 and 1
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40055
        
      28
    You're getting closer, but the base case is probably not when you split 2 into 1 1. You will have cases beyond that, when you get to 1. What you want is to have a base case when you can't split your numbers any smaller and still have them make sense.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: help in solving recursive problems??