C++程序使用递归打印字符串的反转

编写一个递归函数来打印给定字符串的反转。

代码：

//C++程序使用递归反转字符串
#include <bits/stdc++.h>
using namespace std;

/* Function to print reverse of the passed string */
void reverse(string str)
{
    if(str.size() == 0)
    {
        return;
    }
    reverse(str.substr(1));
    cout << str[0];
}

/* Driver program to test above function */
int main()
{
    string a = "Geeks for Geeks";
    reverse(a);
    return 0;
}

//该代码由rathbhupendra贡献```

输出：

skeeG rof skeeG

说明： 递归函数（反转）以字符串指针（str）作为输入，并使用传递指针的下一个位置（str+1）调用自身。当指针到达‘\0’时，堆栈中积累的所有函数都会打印传递位置（str）处的字符，然后一个接一个地返回。

时间复杂度： O(n^2)，因为substr()方法的时间复杂度为O(k)，其中k是返回的字符串的大小。因此，对于每次递归调用，我们将字符串的大小减小一次，这导致类似于（k-1）+（k-2）+……+1 = k*（k-1）/2 = O(k^2) = O(n^2)的系列。

请参见其他反转字符串的方法。

辅助空间： O(n)

有效方法：

我们可以在递归堆栈中存储每个字符，然后可以在返回时打印，如下所示：

//C++程序使用递归反转字符串
#include <bits/stdc++.h>
using namespace std;

/* Function to print reverse of the passed string */
void reverse(char *str, int index, int n)
{
    if(index == n)
    {
        return;
    }
    char temp = str[index];
    reverse(str, index+1, n);
    cout << temp;
}

/* Driver program to test above function */
int main()
{
    char a[] = "Geeks for Geeks";
    int n = sizeof(a) / sizeof(a[0]);
    reverse(a, 0, n);
    return 0;
}