Recursion problem in C

Here is a partial solution in Java: it should be instructive:

public class Join { // prints: static void join(String s, String s1, String s2) { // ABCde if (s1.isEmpty() || s2.isEmpty()) { // ABdCe System.out.println(s + s1 + s2); // ABdeC } else { // AdBCe join(s + s1.charAt(0), s1.substring(1), s2); // AdBeC join(s + s2.charAt(0), s1, s2.substring(1)); // AdeBC } // dABCe } // dABeC public static void main(String[] args) { // dAeBC join("", "ABC", "de"); // deABC } } 

How it works

Basically you have String s, the "output stream", and String s1, s2, the "input stream". At every opportunity, you first take from s1, and later you try again and take from s2, exploring both options recursively.

If at any time either "input stream" is empty, then you're left with no other choice but take whatever's left (if any).

Here it is in C, based on the same idea @polygenelubricants used. It's not that I stole his idea, it's that this is a classical problem and this is the simplest approach :).

#include <stdio.h> #include <string.h> void solve(const char *str1, const char *str2, const int length1, const int length2, char *output, int pozOut, int pozIn1, int pozIn2) { if (pozIn1 == length1 && pozIn2 == length2) { printf("%s\n", output); return; } if (pozIn1 < length1) { output[pozOut] = str1[pozIn1]; solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1 + 1, pozIn2); } if (pozIn2 < length2) { output[pozOut] = str2[pozIn2]; solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1, pozIn2 + 1); } } int main() { char temp[100]; // big enough to hold a solution. solve("ABC", "12", strlen("ABC"), strlen("12"), temp, 0, 0, 0); return 0; } 

This can be improved. For example, how would you get rid of some of the parameters?
Also, this has a bug: you should make sure that output contains a '\0' at the end before printing it, otherwise you might get unexpected results. I'll leave that for you to fix.

I don't feel like I want to write down the whole algorithm. However, here are some leads that might help you.

Basically, you must merge two strings, keeping the characters order. It's like you have 2 stacks of possibly different sizes.

In your example:

stack #1: A B C stack #2: D E 

You also know that the resulting string will have as length the sum of the length of the two input strings. (So you know already how much length to allocate)

If you proceed character by character: each turn you can choose wether to pop one character from either the stack #1 or the stack #2, then continue. (Here could be the recursion). If you roll up all the possible calls you'll have all the resulting strings.

I use to like problems like that when I was in college: it can seem difficult sometimes, but it is so rewarding when you solve it by yourself !

Feel free to comment if you need more clues.

The same algorithm as IVlad, but dynamically allocating the result array, and using pointers rather than indexes making it a bit clearer I think.

#include <stdio.h> #include <stdlib.h> #include <string.h> void solve(const char* result, const char* x0, const char* x1, char* p) { if (!*x0 && !*x1) printf("%s\n", result); if (*x0) { *p = *x0; solve(result, x0 + 1, x1, p + 1); } if (*x1) { *p = *x1; solve(result, x0, x1 + 1, p + 1); } } int main(int argc, char* argv[]) { if (argc >= 3) { size_t total_length = strlen(argv[1]) + strlen(argv[2]) + 1; char *result = malloc(total_length); if (result) { result[total_length - 1] = '\0'; solve(result, argv[1], argv[2], result); free(result); } } return 0; }