递归翻转数组

本文介绍了递归翻转数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

LeetCode 上有这个问题，我无法在 C/C++ 中工作这个想法是使用递归在其位置反转数组(不使用其他附加数组).链接是:leetcode/explore/learn/card/recursion-i/250/principle-of-recursion/1440/解决方案是用 Java 或 Python 完成的.我尝试用C实现解决方案，但总是得到原始数组，我的代码如下:

There is this problem on LeetCode that I can not get to work in C/C++ The idea is to reverse an array in its place (using no other additional array) using recursion. The link is : leetcode/explore/learn/card/recursion-i/250/principle-of-recursion/1440/ The solution is done in Java or Python. I tried implementing the solution in C but I always get the original array, my code is as follows:

void reverseString(char* s, int sSize){ if(!s) return; reverseString(s+1,sSize-1); s[sSize] = *s; }

有些事情我没有考虑到.请让我知道您将如何解决它，如果可能的话，为什么这不起作用.谢谢.

There is something I am not accounting for. Please let me know how would you solve it, and if possible why this is not working. Thanks.

推荐答案

我会尝试一下.

递归解决方案的一般思想是每次调用都获得一个指向字符串开头的指针，以及要查看的字符数，然后走到字符串的中间.

The general idea for a recursive solution is for each call to get a pointer to the start of a string, and how many characters to look at, and this walks its way to the middle of the string.

void reverseString(char *start, int n) { if (n <= 1) return; char tmp = start[0]; start[0] = start[--n]; // the nth character is start[n-1] start[n] = tmp; reverseString(++start, --n); }

每次递归调用时，起始字符串指针加一，长度减二.

On each recursive call, the starting string pointer is incremented by one, and the length decreased by two.

FIRST CALL: v v hello, world SECOND CALL: ^ ^

常见的危险区域是确保它对偶数和奇数长度的字符串做正确的事情.

The common danger area is making sure it does the right thing with even and odd-length strings.

这个方法更简单，只有两个参数，而且 - 正如有些人可能说的 - 更优雅 :-) 即使 ++ 和 --可能被认为是棘手的(一个增量和两个减量).

This method is a bit simpler with just two parameters, and - as some might say - a bit more elegant :-) even if the ++ and -- could be considered tricky (one increment and two decrements).

编辑:这个版本也是尾递归，其中可以通过内部将其转换为循环来进行某些优化.

EDIT: This version is also tail recursive, which can lead to certain optimizations by internally turning it into a loop.