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:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

help in solving recursive problems??

Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
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

author & internet detective
Posts: 41855
904
• Number of slices to send:
Optional 'thank-you' note:
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.

johny doe
Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
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
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

Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
Hello,

Recursive programming is like a stack programming.
so please understand like that so.

author
Posts: 23949
142
• Number of slices to send:
Optional 'thank-you' note:

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

johny doe
Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
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

Marshal
Posts: 79044
375
• Number of slices to send:
Optional 'thank-you' note:
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.

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

johny doe
Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 79044
375
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 41855
904
• Number of slices to send:
Optional 'thank-you' note:
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.

Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 79044
375
• Number of slices to send:
Optional 'thank-you' note:
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.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.