What recursive function can I use to substitute the characters in a string by the greatest character-CodePudding

I got this exercise (it's not homework or an assignment, just practice) that asks for a program that replaces the characters in a string by the greatest character on the right using recursive functions, no loops allowed.

If I have a string acbcba the function has to return ccccba.

One thing I've tried with the loops for the string is this, to maybe try to turn it into a recursion if it worked:

void nextGreatest(char *str, int size)
{
  int max_from_right =  str[size-1];
 
  str[size-1] = -1;
  for(int i = size-2; i >= 0; i--)
  {
    int temp = str[i];
    str[i] = max_from_right;
    if(max_from_right < temp)
       max_from_right = temp;
  }
}

Output: cccba

I think the issue is that it doesn't count the characters that don't have to be replaced.

There was also another example using python I found and tried to change to C (MAX is a macro from here):

void nextGreatest(char *arr, int rev_i, int maxnum){
        if (rev_i == strlen(arr) - 1){
            arr[0] = maxnum;
            return;
        }        
        int i = strlen(arr) - 1 - rev_i;
        arr[i], maxnum = maxnum, MAX(maxnum, arr[i]);
        return nextGreatest(arr, rev_i   1, maxnum);
}

Output: ~bccba

CodePudding user response：

It does not need to be hard:

char nextGreatest(char *s)
{
    char n;
    if (!*s) return 0;
    n = nextGreatest(s   1);
    return *s = MAX(*s, n);
}

If a character is \0 then we've reached the end of the string. Otherwise, we have more characters to the right, and we want the current character to be the greatest of its own value and all values to the right. But since we call the function in this order, you only will need to call it for its direct right neighbour, because it will in turn do the same first.

CodePudding user response：

This is a simple problem of recursion. The idea is, you MUST cross once over the full string to detect what is the maximum and to keep the index the maximum occurred at, and a the second pass over the string to replace some characters at indexes less than the index of the maximum with the maximum you detected at the first loop. I wrote this code for you:

#include <stdio.h>

void
replace_max_char(char*s, char **index, char *max)
{
  if (!*s) return;
  if (*s>=*max)
    *index = s, *max = *s;
  replace_max_char(s 1, index, max);

  if (s<*index)
    *s=*max;
}

int
main(void)
{
  char s[] = "acbcba", *index, max;
  replace_max_char(s, &index, &max);
  printf("%s\n", s);
  return 0;
}

Notice the if (s<*index) after the recursive call of replace_max_char(s 1, index, max). When the recursion finishes, it will start executing the stacked if... and at that moment the maximum is known and also the index the maximum occurred at.