Recursive Functions

Recursion

Sometimes, the solution for bigger instances depends on the solution of smaller instances. A function calls itself for smaller instances until the problem is solved. This approach is called recursion.

Recursive functions in Go

A function that calls itself in its body is called a recursive function. The proverbial example is the calculation of the numbers of the Fibonacci sequence, in which each number is the sum of its two preceding numbers. The sequence starts with:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

How about programming this problem? Consider a number 5, let’s see how recursive functions solve this problem. When we break the problem, we can visualize that:

• Fi(5) = Fib(4)+Fib(3)
• Fi(4) = Fib(3)+Fib(2)
• Fib(3) = Fib(2)+Fib(1)
• Fib(2) = Fib(1)+Fib(0)
• Fib(1) = 1
• Fib(0) = 1

This is a recursive operation. Before coding, look at the illustration to understand in a better way.