need help in C program "of finding all possible Combinations"

[Ahmed sunny]

hello..
i need code for finding all possible combination of repetitive characters using recursion function.
actually the question i s "Imagine a robot sitting on upper left corner of NxN grid. the robot can only move in two direction "Right" and "Down". write a recursive function to find all possible paths that are there for robot?
the above highlighted line is the logic i figured out but i am not able to convert it to C code.
example:
n=3. then there are total 6 possible paths.
path1= RRDD
path2= RDRD
path3= RDDR
path4= DDRR
path5= DRDR
path6= DRRD

so, basicaly i want a recursive function which can do this for any value of N.?

[predator78]

Yes your logic is correct. Now you need to write a recursive function that will produce the same outcome. You figured the logic for the solution but not how to solve for the solution that would be the next step. Write the function now in english like you did for the solution.
ex. robotmove(rightcount,downcount)
if rightcount equals somecondition:
then do stuff possibly call robotmove again with my new parameters?

[iamthwee]

so, basicaly i want a recursive function which can do this for any value of N.?

Yes that is what you want... So get writing.

[Ahmed sunny]

i am not supposed to make the robot move.. i just have to tell its path from upper left corner of grid to lower right. i am trying on it but still failed.
i just can't get the condition right.

[predator78]

That is the name of the function and you could in theory make something move with the code if you had something to move. If it's following a path it is moving from one position to another to find it's way.

[Ahmed sunny]

i have made a program in which '*' is moved by 'r' and 'd' , right and down respectively. whenever any key is press it increments in it. using gotoxy(r,d).

[predator78]

That's possibly your first mistake. The robot doesn't need any help from a user pressing a key. You simply call the function and the robot runs through every possible path with no input other than the algorithim you use in the function.

[Ahmed sunny]

can you please provide a little piece of code involving condition required.i am quite confused . and i have to done it before morning and right now its 3am.

[Uzair Malik]

i also need help with this..... logically this is all correct but i don't know how to convert it into the coding and make exact condition help me out plz

[predator78]

How about if(rightcount<2){rightcount++;movestring+='R'} for starters then we can say robotmove(rightcount,downcout);. That should get you pointed in a direction.

[L7Sqr]

i also need help with this..... logically this is all correct but i don't know how to convert it into the coding and make exact condition help me out plz

A recursive function calls itself usually moving toward some halting condition

void function(int arg) {
   if (arg > 0) {
      function (arg - 1);
   }
}

In the above example the halting condition is arg <= 0 .

It is possible for a function to recurse on itself multiple times.

void function (...) {
   if (...) {
      function (...);
      function (...);
   }
}

Consider that when you are designing a path through a matrix - when you have two possible paths at each grid location.
For example, given the following grid:

+-+-+
| | |
+-+-+
| | |
+-+-+

You could start a recursive call in the top left portion of the grid

/* Assume: void traverse (int row, int col); */
traverse (0, 0);

That would start you at

+-+-+
|*| |
+-+-+
| | |
+-+-+

From there you would head either right or down. So,

traverse (int row, int col) {
   traverse (row + 1, col); /* go down one step */
   ...
}

Which would put you in the following location:

+-+-+
| | |
+-+-+
|*| |
+-+-+

Where your only move would be to the right.

traverse (int row, int col) {
   if (can still go down) /* this fails in your current position */
      traverse (row + 1, col); 
   if (can still go right)
      traverse (row, col + 1); /* go to the right */
   ...
}

Putting you in the following location

+-+-+
| | |
+-+-+
| |*|
+-+-+

Where you can no longer go down or right - the first full path from origin to end: DR

If you work this out on paper similar to how I have started you above you may find that the solution will become clear. Often times trying to design code for a solution that you have not mapped out only serves to confuse you.

[Ahmed sunny]

thanks thats very helpful.
one more thing , after finding 1st path how will function reset itself for second path?

[L7Sqr]

thanks thats very helpful.
one more thing , after finding 1st path how will function reset itself for second path?

It's part of the recursive process. Consider the example above, at position

+-+-+
| | |
+-+-+
| |*|
+-+-+

At that point in the code you are at the following

traverse (0,0)
-- traverse (1, 0) /* move down 1 */
-- -- traverse (1, 1) /* move right 1 */

The -- marks represent each recursive call to the function. So -- -- means that you are two levels deep in the recursion. After you can no longer go right or down the function will return. Returns are represented with <-- in the following

traverse (0,0)
-- traverse (1, 0) /* move down 1 */
-- -- traverse (1, 1) /* moved right 1 */
      <-- /* can not go right or down */
-- traverse (0, 1) /* move right 1 */

And so on until all paths are realized.

[predator78]

That is all in the design of your function. You are setting the condition statements so make sure it keeps going until all paths have been traversed. A recursive function is basically a loop, how would you go about finding every possible combination of numbers in a loop?

[predator78]

*hint*
00
01 we hit the wall here by moving to the right
10 if we reset the right variable here we can try again moving down first
11