# recursion function

• 06-05-2003
jdr30
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 ???
• 06-05-2003
kuphryn
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
• 06-05-2003
XSquared
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.
• 06-05-2003
jdr30
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?
• 06-05-2003
XSquared
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```
• 06-05-2003
jdr30
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!!!
• 06-05-2003
Xei
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.
• 06-05-2003
Zach L.
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