posted 10 years ago
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.
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.
[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
johny doe
Ranch Hand
Posts: 78
posted 10 years ago
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 (max1) and 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max1," ",1);
}
for the case of max and (max2) and 2
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max2," ",2);
}
for the case of max and (max2) and 1 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max2," ",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(maxi," ",i);
}
}//end for
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 (max1) and 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max1," ",1);
}
for the case of max and (max2) and 2
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max2," ",2);
}
for the case of max and (max2) and 1 1
Public static void partitions (int n, int max, String prefix)
{
System.out.println(max);
System.out.println(max2," ",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(maxi," ",i);
}
}//end for
posted 10 years ago
Don't want to rub salt on the wound, but I think that you may have hurt yourself by taking a shortcut 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 redo 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
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 shortcut 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 redo 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
posted 10 years ago
Please take it easy. We have all been there, done that, and got the teeshirt. 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 simplestofall 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 halfdone 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 ]
Three features which all recursive functions display:
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 halfdone 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
Posts: 78
posted 10 years ago
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(n1,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 (ni, i, prefix+" "+i);
}
}
}
i cant undestand the logic behiמd it
i realy tried to figure it out
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(n1,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 (ni, i, prefix+" "+i);
}
}
}
i cant undestand the logic behiמd it
i realy tried to figure it out
Campbell Ritchie
Marshal
Posts: 59438
187
posted 10 years ago
I am afraid you haven't cracked it. I tried it and got a printout rather like this:
So I pushed ctrlC.
Please use code tags round code, and use crtlC/ctrlV 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.
Rclick the project, create a package.
Rclick 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
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
So I pushed ctrlC.
Please use code tags round code, and use crtlC/ctrlV 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.
Rclick the project, create a package.
Rclick 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
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
posted 10 years ago
Johny,
You found a smaller problem:
partitions(n1,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.
You found a smaller problem:
partitions(n1,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.
[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
Malayathi Partha Saradhi
Greenhorn
Posts: 10
posted 10 years ago
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(i1)*i
}
}
this is the recurive program of factorial.
STACK:
The evaluation of i1*i,like that,
method(61)*i > i=6
method(61) calls method() itself.
so method(51) is called i=5;
then method(41) ....so on.
atlast method(1) is called .In this situation 1 is returned by method(1);
In situation ,multiplication will be done.
method(21)*i .........
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(i1)*i
}
}
this is the recurive program of factorial.
STACK:
The evaluation of i1*i,like that,
method(61)*i > i=6
method(61) calls method() itself.
so method(51) is called i=5;
then method(41) ....so on.
atlast method(1) is called .In this situation 1 is returned by method(1);
In situation ,multiplication will be done.
method(21)*i .........
johny doe
Ranch Hand
Posts: 78
posted 10 years ago
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 (number1) and the (MAXnumber)
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
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 (number1) and the (MAXnumber)
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: 59438
187
I am not young enough to know everything.  Oscar Wilde This tiny ad thinks it knows more than Oscar:
Why should you try IntelliJ IDEA ?
https://coderanch.com/wiki/696337/IntelliJIDEA
