# Go Recursion

In Programming, Recursion is a programming technique where the function or an algorithm calls itself one or more times until a specific condition is met.

Go supports recursion. Any function that calls itself is called as a recursive function. For Example:

``````func sum() {
// function body
//...
sum()
}``````

In the above example, we have a function named `sum()`, and inside the function body, we call the `sum()` method itself.

In mathematics, it is common to define functions recursively. For example, the factorial function is defined as:

• 0! = 1
• for all n > 0, n! = n * (n - 1)!

Similarly, the Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• for all n > 1, F(n) = F(n - 1) + F(n - 2)

What they have in common is that they are defined in terms of themselves. And you can do similar things in Go.

## Recursive factorial in Go

``````package main

import "fmt"

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

func main() {
fmt.Print(factorial(5))
}
``````

Output

``120``

This is very similar to the mathematical definition.

Note: The `if` statement is fundamental to the definition, and it acts as a stop condition; otherwise, the function would never stop and goes to infinity:

• `factorial(1)` would call `factorial(0)`,
• `factorial(0)` would call `factorial(-1)`,
• `factorial(-1)` would call `factorial(-2)`,

It is called a base case.

## Recursive Fibonacci in Go

If you want to use a recursive function to compute the nth Fibonacci number, you need a base case for `n == 0` and `n == 1`:

``````package main

import "fmt"

func fibonacci(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
fmt.Print(fibonacci(15))
}
``````

Output

``610``

But this is not efficient at all. Let's say if we need to find fibonacci of 5

• `fibonacci(5)` calls `fibonacci(4)` and `fibonacci(3)`,
• `fibonacci(4)` calls `fibonacci(3)` and `fibonacci(2)`,
• `fibonacci(3)` calls `fibonacci(2)` and `fibonacci(1)`,
• `fibonacci(2)` calls `fibonacci(1)` and `fibonacci(0)`,
• `fibonacci(2)` calls `fibonacci(1)` and `fibonacci(0)`,
• `fibonacci(3)` calls `fibonacci(2)` and `fibonacci(1)`,
• etc.

This is a case of a double recursion, which leads to exponential complexity. A better way is to use a for loop:

``````func fibonacci(n int) int {
x, y := 0, 1
for i := 0; i < n; i++ {
x, y = y, x+y
}
return x
}``````

So be careful when you choose recursion, it can be slow if you don't use it properly. The rule of thumb is to avoid recursive functions when they are multiple calls to the function itself.