# help in solving recursive problems??

johny doe

Ranch Hand

Posts: 78

posted 9 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] [Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [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 9 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 (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

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

Posts: 10

posted 9 years ago

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

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

Campbell Ritchie

Marshal

Posts: 52516

118

posted 9 years ago

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 There is a simplest-of-all case, called the 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 ]

Three features which all recursive functions display:

*n*- 1 rather than

*n*.

*base case*where the recursion stops, otherwise it goes on for ever. A base case commonly has 0 or 1 as an argument.

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

Posts: 78

posted 9 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(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

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: 52516

118

posted 9 years ago

I am afraid you haven't cracked it. I tried it and got a print-out rather like this:

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

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 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 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

*f*5

*f*6 and

*f*7 for step into step over and step return (I think).

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 9 years ago

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.

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.

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

Malayathi Partha Saradhi

Greenhorn

Posts: 10

posted 9 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(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 .........

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

posted 9 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 (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

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: 52516

118