recursion function

This is a discussion on recursion function within the C++ Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    jdr30
    Guest

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

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    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

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Last edited by XSquared; 06-05-2003 at 03:09 PM.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    jdr30
    Guest
    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?

  5. #5
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  6. #6
    jdr30
    Guest
    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!!!

  7. #7
    Xei
    Xei is offline
    Registered User Xei's Avatar
    Join Date
    May 2002
    Posts
    719
    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.
    "What are you after - the vague post of the week award?" - Salem
    IPv6 Ready.
    Travel the world, meet interesting people...kill them.
    Trying to fix or change something, only guaruntees and perpetuates its existence.
    I don't know about angels, but it is fear that gives men wings.
    The problem with wanting something is the fear of losing it, or never having it. The thought makes you weak.

    E-Mail Xei

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Change this program so it uses function??
    By stormfront in forum C Programming
    Replies: 8
    Last Post: 11-01-2005, 07:55 AM
  4. Question..
    By pode in forum Windows Programming
    Replies: 12
    Last Post: 12-19-2004, 06:05 PM
  5. Replies: 5
    Last Post: 02-08-2003, 06:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21