# can someone help me out with recursion

• 05-12-2003
JOsephPataki
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.
• 05-12-2003
DavT
Show us what you've got so far...
• 05-12-2003
Magos
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.
• 05-12-2003
JOsephPataki
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); }```
• 05-12-2003
Magos
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 ;).
• 05-12-2003
GoodStuff

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
• 05-12-2003
Magos
0! = 1
• 05-12-2003
JOsephPataki
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.. :(
• 05-12-2003
JOsephPataki
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);         } }```
• 05-12-2003
JOsephPataki
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.
• 05-13-2003
Hammer
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! :D