0

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
tylerdjt
  • 11
  • 4

3 Answers3

1

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.

Cheatah
  • 1,825
  • 2
  • 13
  • 21
  • If `MAX` is a macro, you better make sure it only evaluates each argument once. – rici Feb 12 '22 at 20:30
  • I see the problem. I will edit my code. I think it wasn't too bad, but it did contain some useless double function calls. – Cheatah Feb 12 '22 at 20:40
  • If MAX is the usual `#define MAX(X,Y) (((X) > (Y)) ? X : Y)`, which evaluates its second argument twice on equality, then your original version did 2^n recursive calls, where `n` is the length of the string. That's not just "some" useless calls. – rici Feb 13 '22 at 07:39
1

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.

alinsoar
  • 15,386
  • 4
  • 57
  • 74
1

think on it as an induction. first define the recursive function well the function get an arr of chars and switch the letter to the greatest from right.(you can define whatever you want) we will do the recursive on the length of the arr(we can call it n, same as induction)

base: n=0 , array with only null charecter, just return the arr. step: lets say if we send arr with length n-1 the function will work so what we nees to do for n? we simply need to look ob the first letter and check what is greatest from right and switch to it.

lets look on example: for acbcba, if we call on smaller arr, cbcba, the return will be cccba(since we assume it works for n-1), now we need to solve for n, so now we have arr acccba, so we look on the first letter and aee what is greatest from it, and then return it.

now try to code it.

Moshe Levy
  • 174
  • 9