Заменить цикл рекурсией

Question

Есть функция, проверяющая массив типа char на симметрию, необходимо заменить цикл for в функции на рекурсию. Подскажите пожалуйста, как это можно сделать, если не затруднит, с примером.

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

bool Simm(char str[]) {
    for (int i = 0, j = strlen(str) - 1; i < j; i++, j--) {
        if (str[i] != str[j]) {
            return false;
        }
    }
    return true;
}

int main() {
    setlocale(0, "");
    srand(time(0));
    
    char str[] = "kazak";
    cout << (Simm(str) ? "Симметрично" : "Не симметрично") << endl;

    char str2[] = "no";
    cout << (Simm(str2) ? "Симметрично" : "Не симметрично") << endl;

    system("pause");
    return 0;
}

Answer 1

Например вот так:

//Простая реализация, но не очень красивая
bool isPalindrome(char str[], int index, int size) {
    if (index > size / 2) 
        return true;
    if (str[index] != str[size - index - 1]) 
        return false;
    else
        return isPalindrome(str, index + 1, size);
}

Или вот так:

bool isPalindromeF(char* str, int start, int finish) {
    if (start >= finish)
        return true;
    if (str[start] != str[finish])
        return false;
    else
        return isPalindromeF(str, ++start, --finish);
}

Ну или можно вот так:

bool isPalindromeS(char* start, char* finish) {
    //Если мы уже проверили часть строки или start и finish
    //указывают на середину строки
    if (start >= finish) 
        return true;
    //Если символы не равны, то строка точно не симметрична (не палиндром)
    if (*start != *finish)
        return false;
    else
        return isPalindromeS(++start, --finish);
}

Пример использования:

int main() {
setlocale(LC_ALL, "Russian");
char str[] = "kazak";
cout << (isPalindrome(str, 0, strlen(str)) ? "Палиндром" : "Не палиндром") << endl;

char str1[] = "onno";
cout << (isPalindromeF(str1, 0, strlen(str1) - 1) ? "Палиндром" : "Не палиндром") << endl;

char str2[] = "kkl";
cout << (isPalindromeS(str2, str2 + strlen(str2) - 1) ? "Палиндром" : "Не палиндром") << endl;

char str3[] = "onjo";
cout << (isPalindromeF(str3, 0, strlen(str3) - 1) ? "Палиндром" : "Не палиндром") << endl;

char str4[] = "kkkllldlfoldlllkkk";
cout << (isPalindromeF(str4, 0, strlen(str4) - 1) ? "Палиндром" : "Не палиндром") << endl;
return 0;
}

Answer 2

Сохраним сигнатуру функции

bool Simm_help(char* str, int begin, int end)
{
    if (begin >= end) return true; // условия выхода с рекурсии
    if (str[begin] != str[end]) return false;
    return Simm_help(str, begin+1, end-1); // собственно рекурсия
}

bool Simm(char* str)
{
    int len = strlen(str);
    return Simm_help(str, 0, len-1);
}

Строка есть палиндромом, если крайние символы равны и после их откусывания также остается палиндром.

БЛОГ НА HUSL

Заменить цикл рекурсией

Ответы (2 шт):