Как понять рекурсивность этой функции?

Question

Это программа для поиска наименьшего числа символов, которые должны быть вставлены (в любой позиции) для преобразования данной строки в палиндром. Может кто-нибудь объяснить мне, что происходит более подробно внутри функции палиндрома? Мне трудно понять рекурсивную функцию, вызываемую снова внутри условия else. Спасибо!

#include <stdio.h>
#include <string.h>


int min(int a, int b) 
{ 
    if(a > b)
        return b;
    else
        return a;
} 

int palindrome(char string[], int l, int h) 
{
    if (l >= h)
        return 0; 
    if(string[l] == string[h])
        return palindrome(string, l+1, h-1);
    else
    {
        int choice1 = 1 + palindrome(string, l+1, h);
        int choice2 = 1 + palindrome(string, l, h-1);
        return min(choice1, choice2);
    }  
} 

int main() 
{ 
    char string[20];
    printf("ENTER STRING: ");
    scanf("%s", string);
    printf("%d", palindrome(string, 0, strlen(string) - 1)); 
    return 0; 
} 

Answer 1

Этот фрагмент кода решает следующую проблему:

Вам дана строка. Сколько символов вы должны вставить в него, чтобы сделать его палиндромом?

Есть хороший набор наблюдений, которые мы можем сделать, чтобы решить эту проблему. Для начала обратите внимание, что любая строка длиной ноль или единица уже является палиндромом. В результате, если нас попросят добавить символы в строку нулевой или нулевой длины, нам вообще не нужно добавлять никаких символов. У нас уже есть палиндром! Это дает нам наш базовый случай:

Базовый случай : Любая строка нулевой или нулевой длины не требует добавления дополнительных символов для создания палиндрома.

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

Итак, давайте начнем с глядя на первый и последний символы нашей строки. Либо они совпадают, либо нет. В случае, если они совпадают, мы в хорошей форме! Нам не нужно добавлять какие-либо конкретные c символы, чтобы эти два символа специально соответствовали друг другу. На этом этапе все, что нам нужно сделать, это убедиться, что остальные символы - те, что внутри - соответствуют друг другу. Это дает нам еще один простой случай для рассмотрения:

Рекурсивный случай 1: Если первый и последний символ строки совпадают, представьте, что их нет, а затем рекурсивно вычислите количество символов, необходимое для того, чтобы сделать средние символы строки палиндромом.

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

a - - - - - - - - - - - - - - - - - - b

Теперь, что должно произойти, чтобы создать эту строку палиндром? Что ж, нам нужно будет вставить хотя бы один символ, чтобы все совпало, так как нам нужно, чтобы первый и последний символы были одинаковыми. Однако есть два способа сделать это. Первый вариант - добавить a в конец строки, например:

a - - - - - - - - - - - - - - - - - - b a

Если бы мы поместили здесь a , то, используя приведенное выше правило, мы сказали бы, что первый и последний символы совпадают, поэтому мы могли бы опустить первый и последний символы и посмотреть, что осталось :

- - - - - - - - - - - - - - - - - - b

Эффект net в том, что мы по существу отбросили первый символ строки (оригинал a ), добавив еще один символ в строку. Отсюда, мы бы хотели сделать все, что лучше, чтобы сделать остальную часть строки палиндромом.

Другой вариант - поместить b в начале строки:

b a - - - - - - - - - - - - - - - - - - b

Здесь мы можем сопоставить это новое b и старое, дав следующее:

a - - - - - - - - - - - - - - - - - -

Требуется, чтобы мы добавили один символ, а затем мы бы (рекурсивно, конечно) выяснили наименьшее количество символов которые нужно добавить к остальной части строки, чтобы сделать ее палиндромом.

В целом это дает нам следующее правило:

Рекурсивный случай 2: Если первый и последний символы не совпадают, то нам нужно добавить еще один символ, либо спереди, либо сзади, чтобы они совпадали. Поэтому попробуйте отбросить первый символ строки и найти лучший способ продолжить, затем отбросьте последний символ строки и посмотрите лучший вариант оттуда, и выберите тот, который лучше. Не забудьте добавить 1 для вставленного символа!

Теперь, когда вы увидели это описание, можете ли вы сопоставить этот базовый случай и два рекурсивных шага с кодом, которым вы поделились с нами?

Надеюсь, это поможет!