1. Description

Recursion is a method of solving a problem by repeatedly decomposing it into identical subproblems.

Scenarios that require recursion usually have the following characteristics.

  1. the original problem can be decomposed into subproblems and the subproblems are the same as the original problem
  2. there is a clear termination condition

Common applications of recursion are as follows.

  1. recursive data solving (Fibonacci function)
  2. data structure forms with obvious recursive properties such as binary trees, generalized tables, etc.
  3. typical problems for which recursive solutions are applicable (e.g., Hanoi problem)

Recursive algorithms are not commonly used, and in most programming languages they are less efficient and take up more stack space. Stack storage is used at each level of recursive calls, and too many recursions can cause stack overflow. For example, for Python, each function call adds a layer of stack frames, and the stack size is not infinite, resulting in a stack overflow.

2. Examples

2.1. Finding the factorial of a number N

Formula for factorial of data N: $n!=n\times(n-1)\times(n-2)… \times1$

The code is as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package main

import (
    "fmt"
    "time"
)

func Factorial(n int64) int64 {
    if n < 2 {
        return int64(n)
    }
    return n * Factorial(n-1)
}

func main() {
    var n int64
    var number int64 = 1

    fmt.Printf("Input n value: ")
    fmt.Scan(&n)

    var start = time.Now()
    result = Factorial(n)
    var elapsed = time.Since(start)

    fmt.Printf("Factorial %v! result is %v\nTotal times is %v", number, result, elapsed)
}

The output is as follows.

1
2
3

➜  go run main.go
Factorial 25! result is 7034535277573963776
Total times is 298ns

2.2. Fibonacci

Fibonacci is the Fibonacci series, i.e. a special series (0 1 1 2 3 5 8 ...), with the following characteristics.

  • The first two numbers are 0, 1 or 1, 1.
  • The value starting from the third number is the sum of the first two numbers.

Go solves the Fibonacci series function as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package main

import (
    "fmt"
    "time"
)

func Fibonacci(n int) int {
    if n == 1 || n == 2 {
        return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

func main() {
    var number int = 50

    var start = time.Now()
    var result int = Fibonacci(number)
    var elapsed = time.Since(start)

    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}

The output is as follows.

1
2
3

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 40.354931919s

3. Efficiency Comparison

The disadvantages of recursion were stated at the beginning, as its repeated calls can lead to stack overflow, and recursion is not as efficient as a normal loop in most programming languages.

Take the Fibonacci function as an example, rewritten as a loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

package main

import (
    "fmt"
    "time"
)

func main() {
    var number int = 50

    var n1 int = 0
    var n2 int = 1
    var result int = 0

    var start = time.Now()
    for n := 2; n <= number; n++ {
        result = n1 + n2
        n1 = n2
        n2 = result
    }

    var elapsed = time.Since(start)
    
    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)

}

The output is as follows.

1
2
3

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 226ns

It can be seen that the time gap is very obvious, and this is one of the disadvantages of recursive algorithms in practical applications.

4. Tail Call Elimination

As mentioned earlier, the reason for poor performance for recursive calls is that stack storage is used at each level of the recursive call.

Too many stack frames lead to a cresting trend in memory usage, and the idea of optimizing the execution efficiency of recursive calls is to reduce their stack frame generation.

In functional programming languages, language standards often require compilers or runtimes to implement tail call elimination.

A tail call is a function whose last statement is also a statement that returns the calling function (Wiki). An example of tail call elimination for the go language, using Fibonacci as an example, is as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package main

import (
    "fmt"
    "time"
)

func Fibonacci(n int, n1 int, n2 int) int {
    if n == 0 {
        return n1
    }
    return Fibonacci(n-1, n2, n1+n2)
}

func main() {
    var number int = 50

    var start = time.Now()
    var n1 int = 0
    var n2 int = 1
    var result int = Fibonacci(number, n1, n2)
    var elapsed = time.Since(start)

    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}

1
2
3

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 443ns

As you can see, the execution efficiency is almost comparable to the loop writing method.