Thread: can someone help me out with recursion

  1. #1
    JOsephPataki
    Guest

    can someone help me out with recursion

    I get the basic concept, but when I need to apply it to a problem I get stumped.

    Basically I need something that will go like..

    4 3
    4 2
    4 1
    4 0
    3 2
    3 1
    3 0
    2 1
    2 0
    1 0

    The way I have my recursion set up right now it only goes through it and gives me
    4 3
    3 2
    2 1
    1 0

    If anyone can help me out it would be much appreciated.

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    Show us what you've got so far...
    DavT
    -----------------------------------------------

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Code:
    void InnerRecurse(int Depth, int OuterDepth)
    {
       if(Depth < 0) return;
       cout << OuterDepth << " " << Depth << endl;
       InnerRecurse(Depth - 1, OuterDepth);
    }
    
    void OuterRecurse(int Depth)
    {
       if(Depth <= 0) return;
       InnerRecurse(Depth - 1, Depth);
       OuterRecurse(Depth - 1);
    }
    You could merge the two functions into one but then you'd need some flag telling it which one it is.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    JOsephPataki
    Guest
    Ok I took what you did and applied it to my actual problem, but I just re-read my problem and it says to write, A recursive function.
    You said I can merge it into one with flagging, can you give me an example with that?

    Here is the program as it stands now.

    It's suppose to take the string and list all of the two-element subsets.

    Code:
    #include <stdio.h>
    
    #define STRMAX 5
    
    void InnerRecurse(int Depth, int OuterDepth, char theString[STRMAX]);
    void OuterRecurse(int Depth, char theString[STRMAX]);
    
    
    int main(){
    
    	char theString[STRMAX] = "ACEG";
    
    	OuterRecurse(0, theString);
    
    	return 0;
    
    }
    
    void InnerRecurse(int Depth, int OuterDepth, char theString[STRMAX])
    {
       if(Depth > 3) return;
       printf("%c %c\n",theString[OuterDepth],theString[Depth]);
       InnerRecurse(Depth + 1, OuterDepth, theString);
    }
    
    void OuterRecurse(int Depth, char theString[STRMAX])
    {
       if(Depth >= 3) return;
       InnerRecurse(Depth + 1, Depth, theString);
       OuterRecurse(Depth + 1, theString);
    }

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Basically, you put both functions in one and separates them with flagging (Flag == true: InnerRecurse, Flag == false: OuterRecurse).
    Code:
    void Recurse(int OuterDepth, int Depth = 0, bool Flag = false)
    {
       if(Flag == true)
       {
          printf("%d %d\n", OuterDepth, Depth);
          if(Depth < 0) return;
          Recurse(OuterDepth, Depth - 1, true);
       }
       else
       {
          if(OuterDepth <= 0) return;
          Recurse(OuterDepth, OuterDepth - 1, true);
          Recurse(OuterDepth - 1);
       }
    }
    
    int main()
    {
       Recurse(4);
       return 0;
    }
    I'll let you implement the strings though .
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User GoodStuff's Avatar
    Join Date
    Jan 2003
    Posts
    65
    Bad question for learning recursion.

    Better question would be something that codes the functionality of the n! series function.

    n! = n * (n-1)!

    but it stops when n=1 because 1! = 1

    So that:

    10! = 10 x 9!
    9! = 9 x 8!
    ...
    1! = 1

    ie.

    10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

    Say our function is rec(int x)

    rec would call itself with argument (x-1)
    and multiply the result with x
    and return THAT.

    It must return 1 when x = 1 and NOT recurse more, else recurse forever.

    Note that the problem you were trying to solve with recursion would be trivial if solved with a nested loop. Keep in mind that it is important to use the right code for the job.

    Many times, if not always, recursion can be re-coded to be non-recursive. The resulting code is almost always more efficient. Such code may not always be easily understood, though.

    Your ENTIRE problem could be solved like this:

    Code:
     int a=4, x, y; 
    
     for (x=a; x>0; x--)
      for (y=x-1; y>=0;y--)
       printf("%d %d \n",x,y);
    See what I mean?

    Gus
    Last edited by GoodStuff; 05-12-2003 at 05:33 AM.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    0! = 1
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    JOsephPataki
    Guest

    Cool

    Well actually, the chapter starts out going over how to turn multiplication into addition with recursion. It moved on to factorials and I got to the end of the chapter and am trying to do some of the programming projects. But now that I responded to you I forgot the question that I came here with..

  9. #9
    JOsephPataki
    Guest

    My next recursion problem

    Well I hope one day I can do this easier, but right now its a pain.

    This next problem is suppose to navigate a maze using recursion. An array 8x8 is suppose to represent the maze. You start out at 0,1 and are suppose to get to 7,7. If a spot equals x then it is a impassable block. Using recursion I'm suppose to print out the path to take and if there is no path I'm suppose to print out that their is no path(I'm not even up to this parts yet).

    Anyways what I _think_ I've done so far is:

    Move right, and if I can't move right I move down, and if I can't move down, I move left to see if I can move down. Right now I set the maze up so that there are no x's and I'm getting through the maze moving straight right then straight down. I tried putting in a road block on the furthest right column earlier to check if I really do move left then down, but I'm not sure its doing that.

    Here is my code - I didn't really comment it yet because I've been doing a lot of deleting of the code. right now x_coord and y_coord functions are there to move you along the maze.

    neighbors tells x_coord and y_coord if they are able to move to left, right, up or down and fill_with_blanks fills the character array in neighbors with blank spaces(since 1's represent if it can move). AND I used recursion to fill it with blanks(at least I did a recursion problem!)

    Code:
    #include <stdio.h>
    
    void x_coord(int x, int y, char maze[8][8]);
    void y_coord(int x, int y, char maze[8][8]);
    void neighbors(int x, int y, char maze[8][8], char x_locals[5]);
    void fill_with_blanks(char x_locals[5], int step);
    
    int main(){
    
    	char maze[8][8];
    
    	for(int a = 0; a <= 7; a++){
    		for(int b = 0; b <= 7; b++){
    			maze[a][b] = ' ';
    		}
    	}
    
    	x_coord(0,1,maze);
    
    	return 0;
    
    }
    
    void x_coord(int x, int y, char maze[8][8]){
    	
    	char x_locals[5];
    
    	neighbors(x,y,maze, x_locals);
    
    	if(x == 7 && y == 7) return;
    	
    	if(x_locals[0] == '1')
    		x_coord(x+1,y,maze);
    	if(x <= 7 && x_locals[0] != '1')
    		y_coord(x,y,maze);	
    
    }
    
    void y_coord(int x, int y, char maze[8][8]){
    
    	char x_locals[5];
    
    	neighbors(x,y,maze,x_locals);
    
    	if(x == 7 && y == 7) return;
    	if(x_locals[2] == '1')
    		y_coord(x,y+1,maze);
    	else if(x_locals[2] != '1' && x_locals[1] == '1')
    		y_coord(x-1,y,maze);
    
    
    }
    
    void neighbors(int x, int y, char maze[8][8],char x_locals[5]){
    
    	fill_with_blanks(x_locals, 3);
    
    	// right, [0]
    	// left, [1]
    	// down, [2]
    	// up,    [3]
    
    	if(x < 7){
    		if(maze[x+1][y] != 'x')
    			x_locals[0] = '1';
    	}
    	if(x > 0){
    		if(maze[x-1][y] != 'x')
    			x_locals[1] = '1';
    	}
    	if(y < 7){
    		if(maze[x][y+1] != 'x')
    			x_locals[2] = '1';
    	}
    	if(y > 0){
    		if(maze[x][y-1] != 'x')
    			x_locals[3] = '1';
    	}
    }
    
    void fill_with_blanks(char x_locals[5], int step){
    
    	if(step < 0){
    	}
    	else{
    		x_locals[step] = ' ';
    		fill_with_blanks(x_locals, step - 1);
    	}
    }

  10. #10
    JOsephPataki
    Guest
    I just added a lot of comments to move code, but since I'm not a registered member I don't think I can edit my post. If anyone wants me to post up the commented code of what I think is doing what then I will.

  11. #11
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    If you're having trouble seeing what your program is actually doing, I suggest you either run it via a debugger, or simply use some printf() statements in key places. Something like:

    printf ("Now entering y_coord() with parms: x=%d, y=%d\n", x, y);

    That way you can at least see the flow of the code.

    >>since I'm not a registered member
    Then register!
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM