Рекурсивно объединять строки с нулевым символом в конце

Question

Я придумываю вопросы интервью, которые требуют анализа кода C ++, который делает что-то простое с указателями и рекурсией. Я пытался написать strcat() рекурсивно:

size_t mystrlen( const char* str )
{
    if( *str == 0 ) {
        return 0;
    }
    return 1 + mystrlen( str + 1 );
}

void mystrcpy( char* to, const char* from )
{
    if( ( *to = *from ) == 0 ) {
        return;
    }
    mystrcpy( to + 1, from + 1 );
}

void mystrcat( char* to, const char* from )
{
    mystrcpy( to + mystrlen( to ), from );
}

Что мне здесь не нравится, так это то, что у меня есть три функции, и мой strcat() не очень рекурсивен - он просто вызывает две другие функции один раз. Есть ли способ переписать это так, чтобы как-то уменьшить количество функций, увеличивающих использование рекурсии, но не жертвуя большей частью краткости кода?

Answer 1

вот мой пример (преимущество в том, что у него только один рекурсивный вызов):

char * mystrcat(char *dest, const char *src){
    if(*dest == 0){
        if(*src == 0)   // end of recursion cond
            return dest;
        *dest = *src++; // actual copy
        dest[1]=0;      // zero out dest buf
    }
    mystrcat(dest+1,src); // advance one char
    return dest;
}

вот примерный тестовый код:

main(){
  char c[]={'a',0,'b','c',0};
  //char c[]={0,'b','c',0};
  mystrcat(c,"xy");
  //mystrcat(c,"");
  puts(c);
}

Answer 2

Ну, я не вижу смысла в том, чтобы пытаться сделать strcat () "настолько рекурсивным, насколько это возможно", хотя это только для вопроса об интервью. strcpy () - это просто strlen () + strcat (), и реализация должна отражать это. Если бы кандидат дал решение, которое вы набросали, я был бы более чем счастлив - он / она показал, что он / она понимает 1. рекурсию и 2. использование подпрограмм для реализации более сложной функциональности.

Answer 3

Как насчет:

void mystrcat( char* to, const char* from )
{
    if (*to == '\0')
        mystrcpy( to, from );
    else
        mystrcat( to + 1, from );     
 }

Answer 4

Однажды у меня возник вопрос на собеседовании, в котором мне пришлось написать простой рекурсивный обход дерева BSP, который представлял собой действительную, невидимую функцию из полной программы.

Я бы предположил, что нечто подобное было бы лучшим способом оценить чье-то понимание рекурсии, чем придумывать проблему, которая идиоматически не решается с помощью рекурсии в C ++. К тому же, кандидатам начального уровня интересно, когда вы запускаете программу, и они замечают, что их код работает безупречно.

Если вы настаиваете на использовании strcat, я думаю, что было бы более интересно, если бы задачей была рекурсивная конкатенация произвольного числа строк, взятых из связанного списка. Даже если операции копирования данных и длины строки не являются рекурсивными, обход связанного списка мог бы быть, и я думаю, что это было бы более интересно, так как вы могли бы на самом деле выполнять работу как в обратном направлении, так и в обратном направлении.

Answer 5

Я подумал о другом ответе!

void
mystrcat(char* to, const char* from)
{
    if (*to)
    {
        // keep looking for end of to
        mystrcat(to+1, from);
        return;
    }

    if (*from)
    {
        // make sure we get past first if
        to[1] = '\0';
        // call recursively until end of from found
        mystrcat(to+1, from+1);
        // after call, copy chars on way out
        *to = *from;
    }
}

Нет дополнительного аргумента для хранения состояния, и оно по-прежнему равно O (n).

Я не уверен, что мог бы придумать это, находясь под давлением собеседования при приеме на работу, однако.

Answer 6

В одной функции вы можете написать:

// pre: to is a string that is zero-initiallized (all chars are '\0')
void mystrcat( char* to, const char* from )
{
   if ( *to ) mystrcat( to+1, from );
   else {
      if (*to = *from) mystrcat( to+1, from+1 );
   }
}

Обратите внимание, что он преднамеренно уродлив, он служит целям в двух ветвях, он продвигает указатель to в первой ветке и копирует значения в другой. Условие if преднамеренно уродливо, так как чаще всего вы будете отмечать одиночное = внутри условия как опечатку, но настаивайте на том, чтобы оно работало, работало и проверялось, чтобы они сами могли разобраться в этом.

Еще одна вещь, которую вы могли бы рассмотреть, это добавить выражение возврата, например:

char* mystrcat2( char* to, const char* from )
{
   if ( *to ) return mystrcat2( to+1, from );
   else {
      if ( *to = *from ) return mystrcat2( to+1, from+1 );
      else return to;
   }
}

Теперь у опрошенной второй задачи - интерпретация результата функции при вызове двух строк, и вы можете обсудить, как эффективность этой версии strcat сравнивается с оригиналом как с точки зрения объединения строк, так и с точки зрения объединения. несколько конкатенаций (посмотрите на эту статью Джоэла Спольски, в которой, помимо прочего, говорится об алгоритме рисования Шаймеля). Вы можете запросить реализацию этой функции в терминах strcat и mystrcat:

// concatenates a set of strings into a buffer
//
// pre:  to has memory enough to hold all the contents
//       from[i] is a valid C string for all i smaller than n
void mymultiplecat( char* to, const char* from[], int n )
{
   for ( int i = 0; i < n; ++i ) {
      to = mystrcat( to, from[i] );
   }
}

Answer 7

Вы хотите рекурсии и краткости? Вот кое-что, что, я думаю, обладает обоими качествами, не вдаваясь слишком далеко в кодовые гольфы (это не значит, что это не безобразно - это так):

char* myStrcat( char* to, char const* from)
{
    if (!*from) return to;

    if (!*to) *to++ = *from++, *to-- = '\0';

    return myStrcat( to+1, from) - 1;
}

Обратите внимание, что в этой версии добавлена ​​сложность возврата указателя назначения (как в стандарте strcat()).

Вот немного более читаемая версия, которая использует немного меньшую «псевдо-хитрость», как операторы запятой, и уменьшается после увеличения, чтобы восстановить указатель to (комментарий Стивехи побудил меня сделать это по некоторым причинам). Второй взгляд на различные ответы здесь в значительной степени эквивалентен ответу подиума :

char* myStrcat( char* to, char const* from)
{
    if (!*from) return to;  // terminal condition, no more chars to concatenate

    if (!*to) {
        // since we're at the end of the 'to' string, 
        //    append char from 'from'
        //    and 'consume' it from `from`
        *to = *from++;
        *(to+1) = '\0';
    }

    return myStrcat( to+1, from) - 1;
}

Однако, пожалуйста, не связывайте мое имя ни с одним из этого кода (я утверждаю, что украл его у кого-то другого).

Answer 8

Я думаю, что вы сделали. У вас есть две прекрасные рекурсивные функции и вызов из них в одну строку.

Я могу думать только о хакерском способе сделать это даже в одной функции:

void
mystrcat(char* to, const char* from, bool copy_now)
{
    if (!copy_now && *to)
    {
        mystrcat(to+1, from, false);
        return;
    }

    *to = *from;
    if (*to)
        mystrcat(to+1, from+1, true);
}

Это почти не плохо, если вы используете C ++ и вы делаете copy_now необязательным параметром со значением по умолчанию false. Тогда вызывающий может притвориться, что у него нет этого дополнительного бита состояния.

Но если проблема достаточно сложна, чтобы заставить вас обратиться за помощью в StackOverflow, это слишком сложно, чтобы быть разумным вопросом для интервью. Вы могли бы попросить его просто попытаться заставить человека мыслить нестандартно, но не делайте неудачу, чтобы автоматически получить хороший ответ.

Я предлагаю добавить еще одну прекрасную рекурсивную проблему: найдите глубину двоичного дерева.

Учитывая следующую структуру:

typedef struct s_node
{
    struct s_node *pLeft;
    struct s_node *pRight;
} NODE;

написать функцию

int tree_depth(NODE *pNode)

, который возвращает максимальную глубину дерева. Мне на самом деле задавали этот вопрос в одном интервью, и я думаю, что это просто правильный уровень сложности для интервью. Люди, которых вы не хотите нанимать, будут иметь проблемы с этим, и людям, которых вы, возможно, захотите нанять, вероятно, это понравится.

РЕДАКТИРОВАТЬ: я проверил функцию и обнаружил, что она имеет ошибку. В этой версии исправлена ​​ошибка.