Go - 递归

递归是以自相似的方式重复项目的过程。这一概念同样适用于编程语言。如果一个程序允许在同一函数内部调用该函数，

func recursion() {
   recursion() /* 函数调用自身 */
}
func main() {
   recursion()
}

Go 编程语言支持递归，即允许函数调用自身。但在使用递归时，程序员需要小心定义函数的退出条件，否则它将陷入无限循环。

Go 中的递归示例

递归函数对于解决许多数学问题非常有用，例如计算某个数的阶乘、生成 Fibonacci 数列等。

示例 1：在 Go 中使用递归计算阶乘

以下示例使用递归函数计算给定数的阶乘 −

package main

import "fmt"

func factorial(i int)int {
   if(i <= 1) {
      return 1
   }
   return i * factorial(i - 1)
}
func main() { 
   var i int = 15
   fmt.Printf("Factorial of %d is %d", i, factorial(i))
}

上述代码编译并执行后，将产生以下结果 −

Factorial of 15 is 1307674368000

示例 2：在 Go 中使用递归生成 Fibonacci 数列

以下示例展示如何使用递归函数生成给定数的Fibonacci 数列 −

package main

import "fmt"

func fibonaci(i int) (ret int) {
   if i == 0 {
      return 0
   }
   if i == 1 {
      return 1
   }
   return fibonaci(i-1) + fibonaci(i-2)
}
func main() {
   var i int
   for i = 0; i < 10; i++ {
      fmt.Printf("%d ", fibonaci(i))
   }
}

上述代码编译并执行后，将产生以下结果 −

0 1 1 2 3 5 8 13 21 34 

Go 中递归的组成部分

为了更好地理解递归算法，让我们学习以下两个组成部分：基础情况（Base Case）和递归情况（Recursive Case） −

• 基础情况（Base Case）：递归算法中的基础情况是一个或一组条件，用于停止递归。
• 递归情况（Recursive Case）：递归算法中的递归情况是函数调用自身的部分。

为了更好地理解上述两种情况，想象你站在楼梯前，想到达顶部。你可以直接跳到顶部，这称为基础情况；或者如果你在最后一步，或者一步一步走，然后解决剩余台阶的问题，这称为递归情况。

让我们使用递归打印自然数的和。制定一个函数来计算从 1 到 n 的所有自然数的总和，如下所示：

F(n) = 1 + 2 + 3 + 4 + + (n-2) + (n-1) + n

通过图示来了解基础情况和递归情况的概念 −

Go 中的递归类型

In Golang 中，recursion 是一种常见的技术，用于解决函数在处理过程中调用自身的问题。

根据函数调用自身和处理数据的方式的不同，有不同类型的 recursion。

1. 直接递归

直接递归 是一种直接的形式。当函数在其自身主体内调用自身时，就会发生这种情况。

func factorial(n int) int {
   // 基本情况：如果 n 为 0，返回 1。
   if n == 0 {
       return 1
   }
   // 递归情况：将 n 乘以 factorial(n-1) 的结果。
   return n * factorial(n-1)
}

示例

函数 factorial 直接调用自身来计算数字 n 的阶乘。基本情况 (if n == 0) 确保当 n 达到 0 时 recursion 停止。每次递归调用都会缩小问题规模 (n-1)，直到满足基本情况。

package main
import "fmt"

func factorial(n int) int {
   if n == 0 {
      return 1
   }
   return n * factorial(n-1)
}

func main() {
   n := 5
   fmt.Println("Factorial of", n, "is", factorial(n))
}

输出

运行代码并查看其输出 −

Factorial of 5 is 120

2. 间接递归

间接递归 发生在函数调用另一个函数，而该函数随后又调用第一个函数时。它涉及两个或多个函数按照特定顺序相互调用。

func funcA(n int) {
    if n > 0 {
        funcB(n - 1)
    }
}
func funcB(n int) {
    if n > 0 {
        funcA(n - 1)
    }
}

示例

在这个示例中，如果 n 大于 0，funcA 调用 funcB；如果 n 大于 0，funcB 调用 funcA。该过程持续进行，直到 基本条件 (n > 0) 不再满足。

package main
import "fmt"

func funcA(n int) {
    if n > 0 {
        fmt.Println("funcA:", n)
        funcB(n - 1)
    }
}

func funcB(n int) {
    if n > 0 {
        fmt.Println("funcB:", n)
        funcA(n - 1)
    }
}

func main() {
    funcA(3)
}

输出

运行代码并查看其输出 −

funcA: 3
funcB: 2
funcA: 1

3. 尾递归

尾递归 是 recursion 的一种特殊形式，其中递归调用是函数中的 最后操作。这意味着递归调用之后没有其他额外的计算或操作。

func tailFactorial(n int, accumulator int) int {
   // 基本情况
   if n == 0 {
      return accumulator
   }
   // 递归调用
   return tailFactorial(n-1, n*accumulator)
}

示例

当 n 为 0 时，函数停止并返回 accumulator（基本情况） 的值，递归调用是最后的操作，它传递 n 的下一个值和 accumulator（递归情况） 的更新值。

package main
import "fmt"

func tailFactorial(n int, accumulator int) int {
   if n == 0 {
      return accumulator
   }
   return tailFactorial(n-1, n*accumulator)
}

func main() {
   n := 5
   result := tailFactorial(n, 1)
   fmt.Println("Factorial of", n, "is", result)
}

输出

运行代码并查看其输出 −

Factorial of 5 is 120

4. 头递归

头递归 发生在函数在执行任何其他操作之前，在函数的 开头（或“头部”） 进行递归调用时。这意味着首先进行递归调用，然后再执行其他操作。

func headRecursion(n int) int {
    // 基本情况
    if n <= 0 {
        return 0
    }
	// 递归调用
    return n + headRecursion(n-1)
}

示例

在这个示例中，当 n 为 0（基本情况）时函数停止，递归调用 headSum(n-1) 在任何其他操作之前首先执行（递归情况）。

package main
import "fmt"

func headSum(n int) int {
    if n == 0 {
        return 0
    }
    result := headSum(n-1)
    return result + n
}

func main() {
    n := 5
    result := headSum(n)
    fmt.Println("Sum of natural numbers up to", n, "is", result)
}

输出

运行代码并查看其输出 −

Sum of natural numbers up to 5 is 15

5. 相互递归

相互递归 发生在两个或多个函数以 循环方式 相互调用时，在涉及的函数之间形成一个 调用循环。它可以涉及任意数量的函数，但最简单的情况是两个函数相互调用。

func isEven(n int) bool {
   if n == 0 {
      return true
   }
   return isOdd(n - 1)
}

func isOdd(n int) bool {
   if n == 0 {
      return false
   }
   return isEven(n - 1)
}

示例

在这个示例中，为了判断数字 n 是否为偶数，isEven 检查 n-1 是否为奇数；为了判断数字 n 是否为奇数，isOdd 检查 n-1 是否为偶数。这种相互调用持续进行，直到 n 达到 0。

package main
import "fmt"

func isEven(n int) bool {
   if n == 0 {
      return true
   }
   return isOdd(n - 1)
}

func isOdd(n int) bool {
   if n == 0 {
      return false
   }
   return isEven(n - 1)
}

func main() {
   n := 5
   fmt.Println(n, "is even:", isEven(n))
   fmt.Println(n, "is odd:", isOdd(n))
}

输出

运行代码并查看其输出 −

5 is even: false
5 is odd: true

6. 无限递归

无限递归 发生在递归函数没有适当的 basic case 来停止 recursion 时。这会导致函数无休止地调用自身，由于连续的函数调用而引起 stack overflow error。

func infiniteRecursion() {
   // 没有基本情况
   infiniteRecursion()
}

示例

在这个示例中，函数 infiniteRecursion 没有 basic case 来停止 recursion，因此它会导致无限 recursion 而不会停止。

package main
import "fmt"

func infiniteRecursion() {
   fmt.Println("This will run indefinitely...")
   infiniteRecursion()
}

func main() {
   infiniteRecursion()
}

输出

运行代码并查看其输出 −

This will run indefinitely...
This will run indefinitely...
This will run indefinitely...
This will run indefinitely...

7. 嵌套递归

嵌套递归 发生在函数的递归调用本身作为参数包含另一个 递归调用 时，即一个递归调用嵌套在另一个内部。

// 嵌套递归函数
func nestedRecursion(n int) int {
   if n > 100 {
      return n - 10
   }
   return nestedRecursion(nestedRecursion(n + 11))
}

示例

在这个示例中，nestedRecursion 使用另一个递归调用的 结果作为参数 调用自身，创建了一个 复杂的调用树。recursion 持续进行，直到最内层的调用满足 basic case。

package main
import "fmt"

func nestedRecursion(n int) int {
   if n > 100 {
      return n - 10
   }
   return nestedRecursion(nestedRecursion(n + 11))
}

func main() {
   n := 64
   result := nestedRecursion(n)
   fmt.Println("Nested recursion for", n, "is", result)
}

输出

运行代码并查看其输出 −

Nested recursion for 64 is 91

8. 匿名函数递归

匿名函数 recursion 发生在匿名函数 (lambda function) 调用自身时。这些没有名称定义的函数可以赋值给变量或用作参数，并且可以递归调用自身。

var factorial func(int) int
factorial = func(n int) int {
   // 基本情况
   if n == 0 {
      return 1
   }
   // 递归情况
   return n * factorial(n-1)
}

示例

在这个示例中，赋值给 factorial 变量 的匿名函数调用自身来计算一个数字的阶乘。这演示了如何使用匿名函数进行递归操作。

package main

import "fmt"

func main() {
   var factorial func(int) int
   factorial = func(n int) int {
      if n == 0 {
         return 1
      }
      return n * factorial(n-1)
   }
   
   n := 5
   result := factorial(n)
   fmt.Println("Factorial of", n, "is", result)
}

输出

运行代码并查看其输出 −

Factorial of 5 is 120