Gene wrote:
>
> #include <stdio.h>
>
> void interleave(char *a, int ia, char *b, int ib, char *r, int ir)
> {
> if (ir < 0)
> printf("%s\n", r);
> else {
> if (ia >= 0) {
> r[ir] = a[ia];
> interleave(a, ia - 1, b, ib, r, ir - 1);
> }
> if (ib >= 0) {
> r[ir] = b[ib];
> interleave(a, ia, b, ib - 1, r, ir - 1);
> }
> }
> }
>
Or if you want a solution with an explicit stack, just replace
interleave() above with the following. The tail recursive call has
been manually removed and the other recursive call translated using the
technique of Horowitz and Sahni.
Cheers!
void interleave(char *a, int ia, char *b, int ib, char *r, int ir)
{
int i = 0, ibs[1000], irs[1000];
call:
if (ir < 0)
printf("\n%s", r);
else {
if (ia >= 0) {
r[ir] = a[ia--];
ibs[i] = ib;
irs[i++] = ir--;
goto call;
}
rtn:
if (ib >= 0) {
r[ir--] = b[ib--];
goto call;
}
}
if (i > 0) {
++ia;
ib = ibs[--i];
ir = irs[i];
goto rtn;
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
