# Why is this code not working?

**URL:** <https://discourse.julialang.org/t/why-is-this-code-not-working/37523>\
**Category:** New to Julia\
**Created:** [April 13, 2020, 6:01pm UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523 "2020-04-13T18:01:14Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Nimpa](https://avatars.discourse-cdn.com/v4/letter/n/eb8c5e/32.png) [@Nimpa](https://discourse.julialang.org/u/Nimpa)\
**Post date:** [April 13, 2020, 6:01pm UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/1 "2020-04-13T18:01:14Z")

</div>

The function below is to calculate the fibonacci sequence using get! but i don’t understand why it is not working.

global fib\_cache = Dict{BigInt, BigInt}(0 =\> 0, 1 =\> 1)  
function fib(n::Integer)  
global fib\_cache  
get!(fib\_cache, BigInt(n), fib(n‑1) + fib(n‑2))  
end

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [April 13, 2020, 6:31pm UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/2 "2020-04-13T18:31:46Z")

</div>

You are not checking whether your Fibonacci number is in the cache, I think.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [April 13, 2020, 6:33pm UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/3 "2020-04-13T18:33:34Z")

</div>

First, when you post something like that, it is good to use  
```julia  
code here  
```  
to make the code more readable. It becomes this way:

```julia
global fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
function fib(n::Integer)
    global fib_cache
    get!(fib_cache, BigInt(n), fib(n‑1) + fib(n‑2))
end

```

It is also good to say how the code is not working, with which values did you test? The code finishes in error, with an wrong answer, or does it just never returns?

Second, your problem is that `fib(n‑1) + fib(n‑2)` is not lazy, so it will be computed anyway, even if there is a value in the cache. And as you do not consider negative values, it ends in a “infinite” recursive call with negative values as parameters.

The code below solves this problems:

```julia
fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
function fib(n::Integer)
  n < zero(n) && @error "negative parameter n ($n) for fib"
  global fib_cache
  get!(fib_cache, BigInt(n)) do
    fib(n - 1) + fib(n - 2)
  end 
end

@show fib(0)
@show fib(1)
@show fib(2)
@show fib(3)
@show fib(4)
#@show fib(-1)

```

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [April 13, 2020, 6:35pm UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/5 "2020-04-13T18:35:28Z")

</div>

Perhaps this package could be relevant? [GitHub - marius311/Memoization.jl: Easily and efficiently memoize any function, closure, or callable object in Julia.](https://github.com/marius311/Memoization.jl)

It does what you appear to be doing

---

<div class="post-metadata">

**Author:** ![A.U.M](https://avatars.discourse-cdn.com/v4/letter/a/aeb1de/32.png) [@A.U.M](https://discourse.julialang.org/u/A.U.M)\
**Post date:** [April 15, 2020, 12:06am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/6 "2020-04-15T00:06:31Z")

</div>

I tried his code and it doesn’t work also for positive number ! , I mean the problem is not related to Negative numbers … the code doesn’t work in General

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [April 15, 2020, 12:28am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/7 "2020-04-15T00:28:10Z")

</div>

Hi @A.U.M, If you read this:

> [@Henrique\_Becker](#):
>
> Second, your problem is that `fib(n‑1) + fib(n‑2)` is not lazy, so it will be computed anyway, even if there is a value in the cache. And as you do not consider negative values, it ends in a “infinite” recursive call with negative values as parameters.

this is @Henrique_Becker saying that the problem is _not_ negative input numbers but the fact that you are calling `fib(n-1) + fib(n-2)` whether or not `n` is in your cache, so it just cascades down to `n=-Inf`

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [April 15, 2020, 12:30am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/8 "2020-04-15T00:30:43Z")

</div>

I never said their code worked for zero or positive numbers. I said the code does not work because it is an infinite recursion, and if they did add an exception throw for negative input, they would have perceived the infinite recursion, as it goes from the number that is passed as parameter (that can be a positive one) to negative infinite.

This can be easily checked by adding this assertion:

```julia
@assert n >= zero(n)

```

as the first line of their original code, and now any call to the method will throw the exception even if the parameter is positive.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [April 15, 2020, 12:31am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/9 "2020-04-15T00:31:57Z")

</div>

You beat me to it, XD.

---

<div class="post-metadata">

**Author:** ![A.U.M](https://avatars.discourse-cdn.com/v4/letter/a/aeb1de/32.png) [@A.U.M](https://discourse.julialang.org/u/A.U.M)\
**Post date:** [April 15, 2020, 12:31am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/10 "2020-04-15T00:31:59Z")

</div>

Thank you I didn’t notice this

---

<div class="post-metadata">

**Author:** ![A.U.M](https://avatars.discourse-cdn.com/v4/letter/a/aeb1de/32.png) [@A.U.M](https://discourse.julialang.org/u/A.U.M)\
**Post date:** [April 15, 2020, 12:32am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/11 "2020-04-15T00:32:46Z")

</div>

Thank you :)) I got it

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [April 15, 2020, 12:32am UTC](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/12 "2020-04-15T00:32:53Z")

</div>

Here’s something you can do to have the error demonstrated:

```julia
julia> function fib(n::Integer)
           global fib_cache
           @show n
           if n < -4 
               error("this is broken")
           end
           get!(fib_cache, BigInt(n), fib(n-1) + fib(n-2))
       end
fib (generic function with 1 method)

julia> fib(4)
n = 4
n = 3
n = 2
n = 1
n = 0
n = -1
n = -2
n = -3
n = -4
n = -5
ERROR: this is broken
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] fib(::Int64) at ./REPL[116]:5
 [3] fib(::Int64) at ./REPL[116]:7 (repeats 9 times)
 [4] top-level scope at REPL[117]:1
 [5] eval(::Module, ::Any) at ./boot.jl:331
 [6] eval_user_input(::Any, ::REPL.REPLBackend) at /home/mason/julia/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:86
 [7] run_backend(::REPL.REPLBackend) at /home/mason/.julia/packages/Revise/Pcs5V/src/Revise.jl:1073
 [8] top-level scope at none:0

```

The thing is that `get!` is a function, so to compute `get!(x, y, z)`, julia needs to first know what `x` ,`y` and `z` are, but in this case, `z = fib(n-1) + fib(n-2)`, so to give that value to the third argument of `get!` it then recurses into `fib(n-1)` and `fib(n-2)` respectively. This causes it to neverendingly flow towards `-Inf`