Go Fibonacci is Imperative and here's a functional approach

Site Feedback
#1

The imperative code has mutation, side effects, and is overall not very efficient IMO. Here’s the efficient way:

go package main

import "fmt"

func fib(n int) int {
[tab]if n == 0 {
[tab][tab]return 0
[tab]} else if n == 1 {
[tab][tab]return 1
[tab]} else {
[tab][tab]return (fib(n-2) + fib(n-1))
[tab]}
func main() {
[tab]fmt.println(fib(5))
}
#2

how do i do indentation? otherwise my code is accurate.

#3

use spaces.

#4

Or copy/paste properly intended code.

To the code:

  1. It uses else after a return, most linters complaint on that
  2. it uses the naive approach on fibonacci, which is well known to be inefficient
  3. it is not tail recursive and will therefore blow the stack in any runtime for sufficiently large n.
  4. It is recursive which will blow the stack in golang, as it does not do any automatic optimisation of recursion, tail call or not.

There are more optmized recursive implementations available that are still provably correct, though I’d use neither of them in go, due to the missing TCO. I’d just use the loop based approach that mutates some variables and eventually returns the result.

Be aware that the algorithmic complexity of the naive implementation is O(1.6ⁿ) while more optimised versions are O(n). Therefore you learn the optimized versions pretty early in the algorithmic classes usually…

1 Like
#5

How did you calculate that algorithm complexity? I read some Suzdalnitski, and eventually got convinced that Functional Paradigm is the best Paradigm. I just wanted to see a functional paradigm approach without mutation and side effects. Course I know it’s a poor algorithm, but mutation is never a good thing.

#6

Unless the best possible performance is a good thing. Although mutation does make it harder reason about code and thus guarantee its correctness.

1 Like
#7

What matters more? Performance or good code? Imo, Go is laser fast so good code matters more

#8

If you are going to limit yourself to only FP techniques in Go, lack of TCO, as pointed out by @NobbZ, is a killer (modulo coding a la Tail-Recursion in Go. Recently I picked up the book “Learning… | by Dylan Meeus | Medium)

#9

The answer is, of course: it depends. There are times when performance is king and times when readability might be more important. Give this a read sometime. And keep in mind that Go is, in my experience, much faster than most other garbage-collected languages (other people have experienced this as well). Now imagine you’re running a simulation that requires you to buy time on expensive hardware and the simulation requires a week to run. If you could improve performance by even 10% do you think that would matter?

So, yes, performance matters. If it didn’t, Go probably wouldn’t exist in the first place. That having been said, for something like this that is completely synthetic and will never see production, take your pick. Don’t prematurely optimize things if you don’t need to.

Finally, I could be in the minority here but I think the imperative approach in this case is easier to read/grok than using recursion. But each to their own.

2 Likes
#10

Mutation is not necessarily good, but it’s the quickest and most efficient way usually.

All the functional languages that tell you about immutability try to avoid copying and recreating stuff as much as they can, they rewrite recursion into loops that mutate, as that simply is how computers work internally.

1 Like
#11

I didn’t, others did, follow the link

#12

Trying to do pure FP in Go is working against the language design and philosophy. If pure FP is paramount, then work in a language that’s designed and optimized for it. Maybe you should be working towards becoming PythonGuyWhoLoves{Haskell,F#,OCaml,Idris,Elm,etc}.

1 Like
#13

PythonGuyWhoLovesRust

Rust is a hybrid of functional and imperative combining the best of both worlds, and Python can be optimized via Rust

#14

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.