Principle of Recursion

Print string in reverse order.

You can easily solve this problem iteratively, i.e. looping through the string starting from its last character. But how about solving it recursively?

First, we can define the desired function as printReverse(str[0...n-1]), where str[0] represents the first character in the string. Then we can accomplish the given task in two steps:

1. printReverse(str[1...n-1]): print the substring str[1...n-1] in reverse order.
2. print(str[0]): print the first character in the string.

Notice that we call the function itself in the first step, which by definition makes the function recursive.

Here is the code snippet:

func printReverse(_ string: String) {
    let charArray = Array(string)
    helper(charArray, index: 0)
}

func helper(_ string: [Character], index: Int) {
    guard index < string.count else {
        return
    }
    
    helper(string, index: index + 1)
    print(string[index])
}

Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Here's my solution. I noticed it's only necessary to recurse halfway through the input.

    func reverseString(_ s: inout [Character]) {
        helper(&s, index: 0)
    }
    func helper(_ s: inout [Character], index: Int) {
        guard index < s.count / 2 else {
            return
        }
        helper(&s, index: index + 1)
        s.swapAt(index, s.count - 1 - index)
    }