Recursion on array of arrays

Question

I am learning how to recursively process arrays of arrays. For example, my program takes N strings as an input. Then I build a function rev_print that should print it again but from the end!

#include<stdio.h>
void rev_print(char **, int);

int main(int argc, char *argv[]){
    printf("Parametri - argc = %d\n", argc);
    int i;
    printf("%s\n\n", argv[0]);

for(i = 1; i < argc; i++)
        printf("%s\n", argv[i]);

    printf("\n");

    rev_print(argv, argc);

    return 0;
}

/********** AUX ************/   

void rev_print(char **p, int n){    /*It should print the array backwards*/
    static int i = 0;
    if(n >= 2){
        rev_print(p, n - 1);
        ++i;
        printf("%s\n", *(p + i));
    }
    else
        printf("%s", *(p + n));
}

I tried anything I know, but at this point I am afraid I do now know recursion. print_rev will print the array in the regular order.

I have an hypothesis, that is, my function is not actually changing the memory locations of the strings. Am I correct?

On linux, I run the program with:

./myProgram.x It is a beautiful day

Answer 1

To find a recursive solution, one fruitful approach is often to begin by thinking about how the problem to be solved can be split into smaller and simpler subproblems.

One way of thinking about the problem of printing a list of strings in reverse is to consider that, given such a list, the list can be split into the first string and a list of the remaining strings. Now the list of remaining strings needs to be printed in reverse, after which the first string should be printed. When the list of strings is empty, there is nothing to reverse and nothing to print.

Here is an example rev_print() function. Here str_list is an array of pointers to char, which is terminated with a null pointer. Note that argv is such an array, and this is a convenient way to control iteration over the array.

void rev_print(char **str_list)
{
    if (*str_list) {
        rev_print(str_list + 1);    // reverse print the rest of the list
        puts(*str_list);            // print the first string
    }
}

If it is desired to reverse-print both the list of strings, and the characters within each string, the same approach can be applied. A function, such as rev_print_string(), can be written that splits a string into its first character and the remaining characters. The remaining characters are printed in reverse, after which the first character is printed. When the string is empty, there are no characters to reverse and print.

This function can be used in a rev_rev_print() function, similar to rev_print(). The only difference here is that instead of printing the strings with puts(), the strings are printed with rev_print(). Note that the rev_print() function does not print a newline character, so this is printed in rev_rev_print() after reverse-printing a string.

Here is a complete example program:

#include <stdio.h>

void rev_print(char **str_list);
void rev_rev_print(char **str_list);
void rev_print_string(char *str);

int main(int argc, char *argv[])
{
    for (int i = 1; i < argc; i++) {
        puts(argv[i]);
    }

    char **strings = argv + 1;

    putchar('\n');
    rev_print(strings);

    putchar('\n');
    rev_rev_print(strings);

    return 0;
}

void rev_print(char **str_list)
{
    if (*str_list) {
        rev_print(str_list + 1);    // reverse print the rest of the list
        puts(*str_list);            // print the first string
    }
}

void rev_rev_print(char **str_list)
{
    if (*str_list) {
        rev_rev_print(str_list + 1);   // reverse-reverse print remainder
        rev_print_string(*str_list);   // reverse print the first string
        putchar('\n');
    }
}

void rev_print_string(char *str)
{
    if (*str) {
        rev_print_string(str + 1);   // reverse print remainder of string
        putchar(*str);               // print the first character
    }
}

And here is a sample interaction:

λ> ./reverse It is a beautiful day
It
is
a
beautiful
day

day
beautiful
a
is
It

yad
lufituaeb
a
si
tI

Answer 2

The recursion to print a list in reverse order is much simpler than you have coded. In a nutshell, printing the list in reverse order using recursion works like this:

1. If the list has more than one item, ignore the first item and print in reverse order the rest of the list.
2. Print the first item.

Step #1 is the recursion step. Printing the rest of the list invokes the same function with different arguments. It is important to check the ending condition to avoid entering an infinite recursion. Call the function recursively only if there is a "rest of the list" to print.

Coding it is as simple as this:

void rev_print(char **p, int n)
{
   # 1. Ignore the first item, recursively print the rest of the list, if any
   if (n > 1) {
        rev_print(p + 1, n - 1);
   }

   # 2. Print the first item 
   printf("%s\n", *p);
}