Member 14829607 Ответов: 3

Обратная строка рекурсивно в C с функцией putback


Поэтому в качестве домашнего задания мне нужно рекурсивно реализовать функцию reverseRec. Я не могу использовать какие-либо циклы, но должен использовать функцию putBack в ней, и функция должна что-то возвращать, что делает все излишне сложным.

#include "stdio.h"
#include "stdlib.h"

int length(char *s) {
  int n = 0;
  while(*s != '\0') {
    n++;
    s++;
  }
  return n;
}

void copy(char* s, int n, char* t) {
  int i = 0;
  while(i < n) {
    t[i] = s[i];
    i++;
  }
}

char* putBack(char* s, char c) {
  const int n =  length(s);
  char* r = malloc(sizeof(char) * (n+2));
  copy(s, n, r);
  r[n] = c;
  r[n+1] = '\0';
  return r;
}

char* reverseRec(char *s){     

    if(*s){                   
        reverseRec(s+1);
        s = putBack(s, *(s-1));           //???
    }
    return s;
}


int main() {
printf("%s", reverseRec("ABC"));
}


Что я уже пробовал:

Поэтому после того, как рекурсия достигает конца строки, она возвращается. Если, например, строка "ABC", то она идет ABC-->BC-->C-->/0-->С-->БC-->ОдинДО Н.Э.. Моя идея состояла в том, что я каким-то образом сохраняю начало строки (*s) каждого возвращающегося возврата и добавляю их вместе с функцией putBack к АНАЛИЗ Но я думаю, что это не может сработать, так как это рекурсия, а это значит, что я ничего не могу сохранить из любой глубины рекурсии, потому что это будет переписано, верно? Я чувствую, что мне чего-то не хватает в том, как рекурсии и буферы работают в C, но idk.

3 Ответов

Рейтинг:
23

RickZeeland

Смотрите пример здесь: C упражнения: получить обратную строку - w3resource[^]

Кстати, рекурсия не нужна. вы также можете сделать это так: C упражнения: печать отдельных символов строки в обратном порядке - w3resource[^]


Рейтинг:
1

KarstenK

Когда рекурсия является явной вашей задачей, то вам нужно будет использовать алгоритм "разделяй и властвуй".

Возможным решением может быть то, что вы вызываете свою функцию swap с первым и последним символом* вашей строки, проверяете, что их расстояние больше 1 (неравномерный случай), чем swap и вызов рекурсивный функция со следующей своп-парой.

void swap(char *first, char* last)
{
  int diff = last - first;

  if( diff > 1 ) {
    swap(first + 1, last - 1);
  }
  //swap 
  char c = *first;
  *last = *last;
  *first= c;
}
Надеюсь, вы понимаете этот принцип.


Рейтинг:
1

Member 14839727

пример входной строки "12345" должен стать "54321"
ваш профессор намекнул вам об этом. Рекурсивность разбивает входную строку на более мелкие части, а затем строит их вместе 1 на 1. Это означает, что количество "рекурсивных шагов" равно пяти для входной строки "12345"

Подсказка 1: входными данными для функции reverseRec( ) являются
вход 1: "12345"
вход 2: "2345"
вход 3: "345"
вход 4: "45"
вход 5: "5"

Подсказка 2: выходы из каждого reverseRec( ) являются
вывод 1: "54321"
выход 2: "5432"
выход 3: "543"
выход 4: "54"
выход 5: "5"

Подсказка 3: поскольку reverseRec( ) вызывает сам себя, он возвращает себе значение. Это значение можно использовать.
reverseRec 1( строка ) получает "5434"
reverseRec 2( string ) получает "543" ( вызываемый reverseRec3 возвращает "543" )
reverseRec 3( string ) получает "54" ( вызываемый reverseRec4 возвращает "54" )
reverseRec 4( string ) получает "5" ( вызываемый reverseRec5 возвращает "5" )
reverseRec 5( string ) ничего не получает ( ни один следующий reverseRec не был вызван для получения значения из)

Подсказка 4: Теперь у вас есть набор информации и недостающая цель
данная информация (входные данные) из подсказки 1:
данная информация (выходные данные) из подсказки 2:
возвращаемое значение из подсказки 3:

reverseRec 1( string ) получает "5434", должен вернуть "54321", учитывая входную строку "12345"
reverseRec 2( string ) получает "543", должен вернуть "5432", учитывая входную строку "2345"
reverseRec 3( string ) получает "54", должен вернуть "543", учитывая входную строку "345"
reverseRec 4( string ) получает "5", должен возвращать "54", учитывая входную строку "45"
reverseRec 5( string ) ничего не получает, возвращает 5, учитывая входные данные "5"

Подсказка 5: недостающая цель
вы должны создать [should return "output"] для шага 4,3,2,1
у тебя возвращаемое значение строка ввода, и добивания


Информация составляет 80% работы ;) теперь сядьте и протестируйте некоторые идеи с putback,
или используйте отладчик, чтобы идти шаг за шагом, чтобы увидеть, что происходит, когда.


реверсерек( ) {
// рекурсивная магия