递归算法_字符串反转_20230412

递归算法-字符串反转

1. 前言

递归算法对解决重复的子问题非常有效，字符串反转也可以用递归算法加以解决，递归算法设计的关键是建立子问题和原问题之间的相关性，同时需要确立递归退出的条件；如果递归退出的条件无法确定，那么就会出现爆栈的错误(stack overflow)。

2. 问题描述

给定某个字符串，word=“hello”，通过递归算法实现反转，输出"olleh"字符串。对于递归算法的实现，可以有两种不同的思路，其一是创建一个新的字符串变量，用于保留反转后的字符串；其二是对原字符串直接进行反转，无需借助新的字符串变量。

3. 子问题分析和递归结束结束条件

对于字符串word=“hello”，其子问题可以通过不断降低字符串长度，从而减低字符的数量。对于字符串word,我们可以构建如下子问题，

word=“hello” 作为原始问题，

word="ello"作为第一个子问题，

word="llo"作为子问题的子问题，

word="lo"作为子问题的子问题的子问题，

word="o"作为子问题的子问题的子问题的子问题–递归结束条件；

word=""空串–递归结束条件

通过上面分析，我们可以选择空串作为递归结束条件，或者选择长度为1的串作为递归结束条件。对于问题描述当中提到两种不同思路，它们分别采用不同的递归结束条件，其中一个方法选择空串作为结束条件，原地反转选择长度为1的子串作为递归的结束条件。

4. 借助全新字符串变量的递归算法

设计递归函数f(char *word, char *reversal_word, int *i)，三个变量分别代表原始字符串，反转后的字符串以及记录反转字符串的下标i.

过程中，我们利用word变为空串时候作为结束条件，在递归返回的时候，提取当前word的首字符，然后保存到reversal_word的第i个字符地址中。

为了更方便理解递归过程，采用图示的方式辅助理解，递归永远都是有去有回，这是由栈的性质决定的，因为程序执行的过程有入栈就必须有出栈，只有这样程序才能完整执行。

当遇到空字符的时候，这时候递归需要结束，开始返回，代表开始出栈的过程。

出栈过程中，我们利用word的当前状态，对reversal_word[i]赋值当前的word[0]，最终完成源字符串的反转。

5. 借助全新字符串变量的递归代码实现

递归的过程非常简单，每次把word的指针往前推进1，直至遇到空字符，然后进行回退。

//*i will be set 0 as intial value
void reverse_word(char *word, char *reversal_word, int *i)
{char ch;if(*word=='\\0'){return;}else{reverse_word(word+1,reversal_word,i);reversal_word[(*i)++] = *(word + 0);}
}

在递归过程中，很容易出现一类错误的算法，这里需要提别提醒，希望引起大家的注意，假定把递归体里面的代码更新成如下格式，好像没有什么错误，但是返回的reversal_word的结果为{‘\\0’,‘o’,‘l’,‘l’,‘e’,‘\\0’}仔细分析过程，从C语言角度理解，因为首字符为’\\0’，它等同于空串。

为什么会出现这种情况呢？ 其实道理很简单，原因在于每次word的回退，它其实都提前了一个节拍，因为在递归前word的值已经发生改变，正确的递归中，word+1只是把指针往前推进一步(具体为sizeof(char)字节)，但是当word回退的时候，其word的值仍然和递归入口 处的值保持一致。

else
{word=word+1;reverse_word(word,reversal_word,i);reversal_word[(*i)++] = *(word + 0);
}

6. 自身反转的递归算法

字符串反转，如果不考虑保留原来的字符串，可以借助字符串本身，对其收尾字符进行有效交换，从对原有字符串完成反转。具体原理就是中间字符视作支点，完成两端字符的交换，这个过程可以借助递归完成。其递归的出口是对字符串的长度进行相应的判断，如果长度减少到1，那么就可以出栈，递归可以掉头返回。

具体来看一下示意图，过程中完成三步操作，在指针往前移动之前，先保留指针指向的字符，然后再交换首字符和末端字符，最后把当前的尾字符赋值为空’\\0’，一切完成后，把指针往前推进一步。后面不断重复上面的步骤，直至字符串的长度为1，开始回退（递归出口)

入栈过程

出栈过程

7. 自身反转的代码实现

   当字符串的长度等于1的时候，也就是已经到了原字符串的支点，这个点就是递归的出口，如果再继续反转下去，那么过程结束的时候，又回到原有的状态。

   这个过程中，ch保留首字符是代码成功实现的关键，当递归回退的时候，我们需要利用到递归前保留的ch首字符值，值得一提的是，每个递归中ch属于不同的变量地址，这一点非常关键；另外对于len的长度值的保留的道理也一样，每个递归中的len都属于不同的变量地址。

void reverse_word_2(char *word)
{int len;char ch;len=strlen(word);if(len<=1){return;}else{ch=*(word+0);*(word+0)=*(word+len-1);word[len-1]='\\0';reverse_word_2(word+1);word[len-1]=ch;return;}
}

8. 小结

大量数据结构和算法的实现都依赖递归，无论是深度优先搜索(DFS)还是动态规划(Dynamic programming)，其算法的实现都与递归息息相关。本文采用两种不同的思路，借助递归算法对字符串完成反转，更清晰理解了递归的具体过程和基本原理。

其实递归的本质就是分而治之，大事化小，小事化了，从最基础的子问题倒退建立解的过程。