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;
}
输出:
skeeG rof skeeG
时间复杂度: O(n),其中n是字符串的大小
辅助空间: O(n),其中n是字符串的大小,将在递归的函数调用堆栈中使用。