Recursive Function not working right

Thread view:

judith - 24 Oct 2006 02:24 GMT

> Hello anyone that can help. This program is suppposed to be written
> with a recursive method and i'm having problems understanding how to do
> this. These are the instructions
>
> There are n people in the room , where n is an integer greater than or
> equal to 1. Each person shakes hands once with every other person .
> what is the total number h(n) of handshakes? Write a recursive function
> to solve this problem. To get you started, if there are only one or two
> people in the room, then.
> handshake(1) = 0
> handshake(2) = 1
> handshake(3) = 3
> handshake(4) = 6
> handhshake(5) = ?
> handshake (6) = 15
> if a third person enters the room she must shake hands with each of the
> two people already there. This is two handshakes in addition to the
> number of handshakes that would be made in a room of two people, or a
> total of three handshakes.
> If a fourth person enters the room she must shake hands with each of
> the three people already present. This is three handshakes in addition
> to the number of handshakes that would be made in a room of three
> people, or six handshakes.
> I don't know how to calculate the number of handshakes per num_people.
> This is the program that our instructor wrote and asked us to fill in
> the code . I have made comments where to fill in the code with what i
> wrote. I can't get the program to compile and i don't know if i wrote
> it right there's not much information in the book on this. If anyone can help or make suggestions i would certainly be appreciative. I'm really not sure what i'm doing. Judith Heres the program

// Author:    Judith Spurlock
// Course:    ITSE 2417
// Program No: 4
// Due Date: 11/3/2006
//
// Program Name: program4JS.java

import java.util.*;

public class program4JS
{
    public static int handshakes(int numpeople)
    {
    return numpeople;//fill in code
    }
    public static void writeup(int num_people) //fill in code
    { //fill in code
    if(num_people >=1) //fill in code
    writeup(num_people*(num_people - 1)/2); //fill in code
    }
    //fill in code
    public static void main(String[]args)
    {
    int num_people = 0;
    int num_handshakes = 0;

    Scanner keyboard = new Scanner(System.in);
    System.out.println("How many people are in the room?");//fill in code
    num_people=keyboard.nextInt();

    //fill in code
    num_handshakes = handshakes(num_people);
    System.out.println("If everyone shakes hands once, there will be " +
    num_handshakes + " handshakes.");
    }

}

Here is what it's doing instead of what it should be doing i'm not sure
how to write it

C:\>java program4JS
How many people are in the room?
1
If everyone shakes hands once, there will be 1 handshakes. //should be
0

C:\>java program4JS
How many people are in the room?
2
If everyone shakes hands once, there will be 2 handshakes. //should be
1

C:\>java program4JS
How many people are in the room?
3
If everyone shakes hands once, there will be 3 handshakes. // should be
3

C:\>java program4JS
How many people are in the room?
4
If everyone shakes hands once, there will be 4 handshakes. //should be
6

C:\>java program4JS
How many people are in the room?
6
If everyone shakes hands once, there will be 6 handshakes. //should be
15

C:\>

Reply to this Message

goelshek@gmail.com - 24 Oct 2006 02:54 GMT

You don't need recursion here. Following works.

> public class program4JS
> {
[quoted text clipped - 18 lines]
>
> }

Reply to this Message

judith - 24 Oct 2006 03:01 GMT

> You don't need recursion here. Following works.
>
[quoted text clipped - 20 lines]
> >
> > }

My programs working now thanks for all the help

Reply to this Message

Patricia Shanahan - 24 Oct 2006 03:26 GMT

>> You don't need recursion here. Following works.
>>
[quoted text clipped - 22 lines]
>
> My programs working now thanks for all the help

Does it meet the requirements? The base message of this thread said
"This program is suppposed to be written with a recursive method".

Generally, problems that are simple enough for teaching recursion to
beginners can also be solved without recursion. If you were asked for
recursion, just calculating the series sum may not be appropriate.

Patricia

Reply to this Message

quetzalcotl@consultant.com - 24 Oct 2006 12:29 GMT

> You don't need recursion here. Following works.

I don't think you are helping Judith the way she needs it.
Obviously her problem is to find a solution (not just to copy + paste a
working one), and the handshake thing is a nice example for learning
how to think about problems that lend themselves to a recursive
solution.

a) find the base case

The simplest possible handshake problem is, when there is only one
person. You would not shake your hands with yourself, so we have

static int handshakes(int persons) {
if (persons <= 1) return 0; // we subsume the case of less than 1
person

b) find the induction rule

Now suppose in a room there are a number n of people who already have
shaked hands. We call the number of handshakes that took place so far
handshakes(n). How many hands must a new person shake? Of course, n (by
shaking hands with everybody who is in the room). Therefore, we find
that handshakes(n+1) == handshakes(n)+n
We are now ready to write this in java:
int n = persons-1; // suppose there were n people in the room;
int h = handshakes(n); // that have shaked hands already
int t = h+n; // and let the persons'th person shake n
hands
// to get the total of handshakes
return t; // which is our result
}

c.) Proof that recursion will terminate

Since the recursion computes handshakes(n) for values that are ever
getting smaller, it must eventually meet the base case, where the
recursion terminates.

Reply to this Message

Andy Dingley - 24 Oct 2006 12:53 GMT

> > This program is suppposed to be written
> > with a recursive method

These are always a pain. Recursive algorithms are non-intuitive (to
most people) and it's hard to produce usably simple examples that are
better implemented recursively than by other ways. Assuming you _must_
do this recursively, then accept that it won't be the best way of doing
it.

Best way for this one is probably analytically. Do some maths, not
programming. Find a simple algebraic expression that sums your
handshake function for any value of n, then implement that (probably in
one line, running very quickly).

Anyway, to recursion!

Most recursive algorithms have the following characteristics:
There's a function foo() which calls itself. Sometimes they're indirect
( foo() calls bar(), then bar() in turn calls foo() ) but those are
even more awkward.

foo() either calls foo(), or it doesn't (and then it just returns).
Getting this test right is important!

You have lots of ways to pass information into a function call, not
many ways to get information back (just the fuinction return). You also
don't have much ability to see bucketloads of "global" (sic) data. So
design your algorithm around these limits and embrace them, don't fight
against them.

Good recursive algorithms typically don't solve complicated problems,
they either solve trivial problems, or else they simplify the problem a
bit and call themselves again to see if it's now trivial enough to
solve directly (remember that question about when foo() halts?)

So (for Java) how can you mangle your problem into an implementation
that can pass possibly many things in, but only needs _one_ value
returned? (you can use or modify this value afterwards)

As a Very Big Hint, solving handshake(1) or handshake(2) sounds pretty
trivial to me....
Solving handshake(n) is probably a lot like handshake(n-1), with
something added to the result that it returned.

Reply to this Message

Lew - 28 Oct 2006 01:34 GMT

>> Hello anyone that can help. This program is suppposed to be written
>> with a recursive method and i'm having problems understanding how to do
>> this. These are the instructions

There are also a lot of responses to this question under the subject line
"new java programmer with compile error and trouble writting a Recursive
Function".

- Lew

Reply to this Message

Recursive Function not working right

Free Magazines