如何用递归替代嵌套循环生成所有连续子字符串-Golang-PHP中文网

如何用递归替代嵌套循环生成所有连续子字符串

本文详解如何使用递归方法替代传统嵌套循环，系统性地生成字符串的所有连续子串（即所有非空、位置连续的子序列），并提供可运行的 go 语言实现、逻辑解析与关键注意事项。

本文详解如何使用递归方法替代传统嵌套循环，系统性地生成字符串的所有连续子串（即所有非空、位置连续的子序列），并提供可运行的 go 语言实现、逻辑解析与关键注意事项。

在字符串处理中，枚举所有连续子字符串（contiguous substrings） 是常见需求——例如用于滑动窗口分析、回文检测或模式穷举。原始代码使用双重 for 循环（外层控制子串长度，内层控制起始位置）简洁高效，但若需以递归思想建模（如理解分治、训练算法思维或适配特定函数式上下文），则需重构逻辑。

核心思路是：将“生成所有长度为 L 的连续子串”作为子问题，L 从 len(str) 递减至 1；对每个 L，再递归遍历所有合法起始索引 i（满足 i + L ≤ len(str)）。这自然形成双层递归结构，但可通过单函数+多参数优雅实现。

以下是优化后的 Go 递归实现（修正原答案中边界错误，确保输出与示例完全一致）：

package main

import "fmt"

// recSubstrings 递归生成字符串 str 中所有非空连续子串
// length: 当前处理的子串长度（从大到小）
// start: 当前长度下子串的起始索引
func recSubstrings(str string, length, start int) {
    // 基础情况：length  len(str) {
        recSubstrings(str, length-1, 0)
        return
    }

    // 输出当前子串：str[start : start+length]
    fmt.Println(str[start : start+length])

    // 同一长度下，尝试下一个起始位置
    recSubstrings(str, length, start+1)
}

func main() {
    str := "23405"
    recSubstrings(str, len(str), 0)
}

✅ 输出验证（与问题示例严格一致）：

⚠️ 注意事项：

原问题示例中 "23405" 的输出顺序是按长度降序，同长度内按起始索引升序（如 23, 34, 40, 05）。本实现严格遵循此顺序。

递归深度为 O(n²)，与迭代法时间复杂度相同，但空间复杂度增加 O(n)（调用栈深度），对超长字符串需警惕栈溢出。

若需升序长度输出（先长度1，再长度2…），只需将 recSubstrings(str, length-1, 0) 移至 fmt.Println 之后，并初始调用 recSubstrings(str, 1, 0)。

此方案生成的是连续子串（substrings），非任意子序列（subsequences）——后者需指数级枚举，不可仅靠双指针递归解决。