Chasing my tail : Can't trace this recursion 
Author Message
 Chasing my tail : Can't trace this recursion

I have spent much time trying to figure out by tracing in my de{*filter*} but to
no success.
I must be missing something big here with recursion.
I can follow it thru the first two out puts but I am can't follow the value
of the variable i.
I'm thinking these functions are piling up in the stack but I am confused
even hand tracing
it in a table format. Any suggestions on how to visualize or hand trace?

The book says " for each character in the string , exchange it with the
strings first character
and generate the permutations of the characters that remain".

Thank You!!!

OUTPUT

0123
0132
0213
0231
0321
0312

/* Joy of C page 477  produce permutations
* generate all permutations of a string
* swap and exchange two characters
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int Len;

  /* length of string to permute */

void permute(const char *s, int pos);

int main(  )
{

 char string[5] = "0123";
 char *strtest;

 int i;

 strtest = string;

 /* DEBUG : fooling with parameters  */

 for (i = 1;  i < 2; i++)
 {
 Len = strlen(strtest);

  permute(strtest, 0);
 }

 return EXIT_SUCCESS;

Quote:
}

void permute(const char *s, int changepos)
{
 void swap(char *ptr1, char *ptr2);

 char *scopy;
 int i;
 int ctr;

 if(changepos < Len)
  for(i=changepos; i < Len; i++)
  {
   scopy = malloc(Len + 1);  /* assumes malloc succeeds */
   strcpy(scopy, s);

   swap(&scopy[i], &scopy[changepos]);
   printf("%i i  %i cp\n", i, changepos);  /* DEBUG print i, cp */

   permute(scopy, changepos + 1);
   free(scopy);
  }

 else

  printf("%s\n",s);

Quote:
}

void swap(char *p, char *q)
{
 char temp;

 temp = *p;
 *p=*q;
 *q = temp;

Quote:
}



Fri, 07 Jan 2005 22:53:32 GMT  
 Chasing my tail : Can't trace this recursion

Quote:
> I have spent much time trying to figure out by tracing in my de{*filter*} but
to
> no success.
> I must be missing something big here with recursion.
> I can follow it thru the first two out puts but I am can't follow the
value
> of the variable i.
> I'm thinking these functions are piling up in the stack but I am confused
> even hand tracing
> it in a table format. Any suggestions on how to visualize or hand trace?

> The book says " for each character in the string , exchange it with the
> strings first character
> and generate the permutations of the characters that remain".

> Thank You!!!

    One technique I've used successfully is to create a global
depth-counter and use it to control the indentation of diagnostic output
from the routine(s).  With this, and a few well-placed printf's, it should
be come obvious what's happening.

    Norm



Sat, 08 Jan 2005 04:04:31 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. MC++ tail recursion optimizer bug in virtual function

2. Tail recursion in C

3. Tail recursion

4. Tail Recursion Optimization in C.

5. Tail recursion in C

6. tail recursion in C

7. Tail recursion optimization

8. Blind Tail Recursion

9. Tail Recursion in C (CBOYER 1.3)

10. Tail Recursion in C Summary of Results

11. Tail Recursion/Continuation-Passing in C

 

 
Powered by phpBB® Forum Software