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

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是字符串的大小,将在递归的函数调用堆栈中使用。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例