# Test benchmark fibonaci recursive/non recursive

Tram Ho

## Test benchmark fibonacci recursive/non recursive

### Motive, reason

Until now, I still have the question that for the same problem between recursive and non-recursive, which one will be the more effective solution. On the occasion of my team members’ code review, everyone talked about recursive / non recursive, so I decided to dig deeper to see if my initial thought was correct.

I have read the documents, almost everyone has the same comment as follows:

Advantages of recursive: Neat, easy to understand, easy to code

Cons: Consume memory space, and processing time due to having to switch context between function calls.

The above are all theoretical comments. From the perspective of a person who is currently an engineer who was a professional student, I only believe when there are experimental results that are specific numbers.

And `go` , it’s pretty easy for me to do this with the test benchmarks tool

Without saying much more, let’s get to the main topic.

## Test benchmarks with fibonacci recursive

First, we implement the algorithm implementation with a recursive approach.

Install benchmark test with input N = 10

Execute the benchmark test with the following command

`go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out`

Result

Comment: Repeat `4973802` times, each time takes `239.1 ns` total `1189236058.2 ns`

My phone is up to `i7` , I just noticed it now

1 billion more in-depth analysis

### Runtime analysis

Run command

`go tool pprof profile.out`

Use the top command to get the most time consuming processing, sorted in descending order

Result

Total running time loss for `FibRecursive` is `1.21s`

Continue in-depth analysis of each command line for the function `FibRecursive`

`(pprof) list FibRecursive`

Result:

Show graph results in png, pdf using command:

`(pprof) web`

End of analysis

`(pprof) q`

### Analysis of memory allocation

`go tool pprof memprofile.out`

`(pprof) web`

## Test benchmarks with fibonacci non recursive

Implement the algorithm with the approach of de-recursion.

Install test benchmark with input N = 10 (same step above)

Optimized

Because the variable `tmp` is allocated in the loop, it increases the memory quite a lot, causing the wrong conclusion. After finding out the cause, I fixed it as follows:

#### Analysis

Continue to run the same command

`go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out`

Result:

there are `223505781` operations each taking 5,321 `5.321 ns` total `1189274260.7 ns`

Optimized

Run command

`go tool pprof profile.out`

`(pprof) top`

Total running time for `FibNonRecursive` is `980ms`

Optimized

Total running time loss for `FibNonRecursive` is `0.90s`

`(pprof) list FibNonRecursive`

Optimized

`(pprof) list web`

Optimized

`(pprof) q`

### Analysis of memory allocation

`go tool pprof memprofile.out`

`(pprof) top`

Optimized

`(pprof) web`

Optimized

## Compare and conclude with the case N = 10

CriteriaRecursiveNon RecursiveNon Recursive Optimized
Time`1.16s``0.01s``0.02s`
Memory`5140.68kB``5811.98kB``3746.37kB`

Note: The memory comparison criterion is not reasonable

Updated

True to the original comment, after optimized `Non Recursive` has a lower running time and takes less memory than `Recursive`

Please test it out let try !!!

### References

Happy coding!!!

Share the news now

Source : Viblo