通过 7 个算法挑战练习递归

还记得第一次自己解决算法难题而没有查找解决方案，却被告知使用递归函数再次解决它吗？

由于这似乎是一种常见的情况，尤其是在技术面试环境中，我整理了一份经典算法挑战列表，以帮助锻炼我们的递归大脑能力，因为这似乎是一种常见的情况，尤其是在技术面试环境中......🙃

挑战列表

反转字符串
添加数字
寻找最大整数
查找特定元素
回文
排列
斐波那契

1. 反转字符串

/* Instruction:
Given a string, write a recursive function to return the reversed string. */

// Example:
reverseString('covid')
// => 'divoc'

这似乎是每个代码新手都会遇到的第一个挑战。如果你还没有用递归解决这个问题，我建议你在继续阅读之前先尝试一下。

这是我的解决方案，可以通过三元运算符重构：

function reverseString(str) {
    // base case: when there's no string to reverse
    if (str === '') {
        return ''
    } else {
    // recursive case: 
    // (1) grab the last character of current string, 
    // (2) call the same function 
    // (3) pass in a substring that does NOT include the last character
    // (4) return (1) + (2)
        return str[str.length - 1] + reverseString(str.substring(0, str.length - 1))
    }
}

2. 添加数字

/* Instruction:
Given an array and an index, write a recursive function to add up the elements of an array. */

// Examples:
addingUpTo([1, 4, 5, 3], 2)
// => 10
// => adding the number all the way up to index 2 (1 + 4 + 5)
addingUpTo([4, 3, 1, 5], 1)
// => 7
// => adding the number all the way up to index 1 (4 + 3)

因为我们要返回多个数字的总和，所以我立即想到声明一个变量sum。

此外，由于我们得到了一个索引，我决定sum以该索引处的元素为起始，并向后添加数字。

基本情况是当我们到达操作的末尾时，在本例中是索引 0，因为我们正在向后添加。

function addingUpTo(arr, idx) {
    // initiate sum at arr[idx]
    let sum = arr[idx]
    // base case: idx === 0
    if (idx === 0) {
        return sum
    }
    // adding backward
    return sum + addingUpTo(arr, idx - 1)
}

3. 寻找最大整数

/* Instruction:
Given an array, write a recursive function to find the largest integer in an array. */

// Examples:
maxOf([1, 4, 5, 3])
// => 5
maxOf([3, 1, 6, 8, 2, 4, 5])
// => 8

这是一个比较题。所以，自然而然地，基准情况是无法进行比较，也就是数组中只剩下一个元素的时候。

现在，我们如何才能继续比较和减少数组中的元素以达到基本情况？

JavaScript 中的方法splice帮助了我。

由于splice方法的可变性，我可以比较数组中的前两个元素，删除较小的元素，然后使用更新后的数组递归调用该函数，如下所示：

function maxOf(arr) {
    // base case: only one element left in arr
    if (arr.length === 1) {
        return arr[0]
    }
    // compare first two elements and remove smaller one
    if (arr[1] > arr[0]) {
        arr.splice(0, 1) // remove arr[0]
    } else {
        arr.splice(1, 1) // remove arr[1]
    }
    return maxOf(arr)
}

4. 查找特定元素

/* Instruction:
Given an array and a number, write a recursive function to see if the array includes the given element. */

// Examples:
includesNumber([1, 4, 5, 3], 5)
// => true
includesNumber([3, 1, 6, 8, 2, 4, 5], 9)
// => false

与函数类似maxOf()，我们需要将数组中的元素与给定的数字进行比较。

一旦找到匹配项，我们可以立即返回true；如果没有，我们可以递归调用该函数并传入数组减去刚刚比较的元素，直到达到基本情况。

我在这里建立的基本情况是当数组中没有剩余元素时，在这种情况下我们返回false，因为数组中没有任何元素与给定的数字匹配。

function includesNumber(arr, num) {
    // base case: no element is left to compare
    if (arr.length === 0) {
        return false
    }

    if (arr[0] === num) {
        return true
    } else {
        let newArr = arr.slice(1)
        return includesNumber(newArr, num)
    }
}

事后看来，我应该使用splice而不是slice方法来删除当前元素。使用slice会在每次递归函数调用中触发数组的新副本，如果数据集较大，这可能会降低操作速度。

5.回文

/* Instruction:
Given a string, write a recursive function to see if a word is a palindrome. */

// Examples:
isPalindrome('madam')
// => true
isPalindrome('covid')
// => false

回文是指如果颠倒每个相反字符的顺序，读起来仍然相同的单词或短语。

我在脑海中以镜子的形式来解决这个问题：比较每个递归函数中字符串的第一个和最后一个字符，直到我们到达中间点，这成为我们的基本情况。

在递归的情况下，false如果当前字符不等于对立字符，我们应该立即返回，因为这不满足回文的组成。

function isPalindrome(str) {
    // base case: reaching midpoint, or empty str
    if (str.length <= 1) {
        return true
    } 

    if (str[0] !== str[str.length - 1]) {
        return false
    } else {
        return isPalindrome(str.substring(1, str.length - 1))
    }
}

6. 排列

/* Instruction:
Given a string, write a recursive function to print out an array of all possible permutations of the string. */

// Examples:
permutations('abc')
// => ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
permutations('aabc')
// => ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]

排列是对一组元素进行重新排列。现在，我们至少需要 2 个元素才能完成排列。如果字符串只有一个或更少的字符，则无需重新排列，因此这就是我们的基准情况。

递归的情况对我来说比较棘手。与之前的挑战不同，这次我们需要多层运算才能达到预期的结果：

function permutations(str) {
    let arr = []
    // base case: less than 2 characters in the string
    if (str.length < 2) {
        arr.push(str)
        return arr
    } 

    for (let i = 0; i < str.length; i++) {
        let currentChar = str[i]
        let remainingStr = str.slice(0, i) + str.slice(i + 1, str.length)
        let remainingPermutation = permutations(remainingStr) // save the result of the recursive function

        // if we find a repeating character, don't add it to the arr
        if (str.indexOf(currentChar) !== i) {
            continue
        }
        // concat currentChar with each substring and push to the arr
        remainingPermutation.forEach(subString => arr.push(currentChar + subString))
    }
    return arr
}

正如代码片段中所注释的，在递归情况下，我们不仅需要考虑给定字符串中存在重复字符的情况，还必须将当前字符与递归函数结果的每个排列连接起来。

如果您仍然感到困惑，我强烈推荐这个详细的演练，它帮助我理解了这个挑战的递归解决方案。

7.斐波那契

/* Instruction:
Given a number, write a recursive function to 
print out the n-th entry in the fibonacci series. 

Fibonacci series is a sequence, 
where each number is the sum of the preceding two: 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] */

// Example:
fib(3)
// => 2
fib(6)
// => 8

我听说不查阅资料就想出递归解决方案的情况并不常见，所以这里提供了“教科书”版本，根据一些经验丰富的开发人员的说法，这是一个值得记住的公式：

function fib(n) {
    if (n < 2) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

这种递归方法的运行时复杂度是指数级的（O(2^n)），因此它的性能不如普通的迭代方法（O(n)）。

您可以利用该memoization技术来优化递归，但这超出了本文的讨论范围。

最后的想法

我们每个人都有不同的方法使用递归来解决问题。我经过多次练习才形成了自己的策略。

到目前为止，我倾向于先弄清楚基本情况，正如多种资源所建议的那样。然后，我会尝试递归情况，这通常涉及创建子任务并合并子任务的结果。

那你呢？你是如何训练你的大脑进行递归思考的？请在评论区留言告诉我！

文章来源：https://dev.to/liaowow/practicing-recursion-with-7-algorithm-challenges-41ik