recursion function

Given two points (x0,y0) and (x1,y1) on the x-y plane. In a north-east
path from (x0,y0) to (x1,y1), one may walk only to the north (up) and to
the east (right). Write a program to count the number of northeast paths
from one point to another.


any ideas how to start this ???

Post an example with real numbers. What if the northeast parth is not the best solution?

(0, 0) <-----> (10, 0)

In the example above, you do not need to walk northeast. Just walk east!

Kuphryn

You're not finding the best path, you're counting the number of paths.

In your example it would return 1.

If it was going from (0, 0) to (2, 2), it would be 6 different paths.

Code:

---

NNEE
NENE
NEEN
ENEN
ENNE
EENN

---

A non-recursive way to calculate it would be:

Code:

---

(deltaX + deltaY)! / (deltaX! * deltaY!)

---

And if deltaX or deltaY is 0, the result is always 1.

I dont know .. that is what he gave us to work with ... I have no idea what any of the code should look like though ... any suggestions?

Here's some pseudocode for the recursive function to get you started:

Code:

---

function recurse takes 2 parameters( x and y )

        declare a variable to hold the number of possibilities = 0

        if the x and y coordinates are the final coordinates then
                return 1
        end if

        if the x coordinate is not the same as x2 then
                call the function again, with x+1 and y as the parameters
                add the return value to the number of possibilities
        end if

        if the y coordinate is not the same as y2 then
                call the function again, with x and y+1 as the parameters
                add the return value to the number of possibilities
        end if

        return the number of possibilities
end function

---

OK .. i understand what you are saying here .. but what is the actual code for the if statement ?? I am new to recursion .. any help is GREATLY APPRECIATED!!!

I find that creating recursive functions can be VERY unstable and put a heavier load on the processor depending on what your calculating, so always make sure that a recursive function is the best method for what you are doing.

Yeah, the call stack on recursive functions can sometimes be absurd.

Often recursive methods are used in teaching (as they do involve very important principles), but are avoided for the reasons Xei mentioned. Unless you know that the depth of recursion will be fairly low, I'd try to avoid it in practice.

Try to work out the code from XSquared's pseudocode. If your still having problems, post what you have so we can help.

Cheers