# Function Problem

**URL:** <https://discourse.julialang.org/t/function-problem/37596>\
**Category:** General Usage\
**Tags:** question\
**Created:** [April 14, 2020, 11:11pm UTC](https://discourse.julialang.org/t/function-problem/37596 "2020-04-14T23:11:02Z")\
**Posts on this page:** 7\
**Page:** 1

<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 14, 2020, 11:11pm UTC](https://discourse.julialang.org/t/function-problem/37596/1 "2020-04-14T23:11:02Z")

</div>

Sorry I am new in Julia , This is my Fibonacci numbers function :

```julia
> global fib_cache = Dict{BigInt, BigInt}(0 => 0, 1 => 1)
> function fib(n::Integer)
> global fib_cache
> if haskey(fib_cache, n)
> fib_cache[n]
> else
> fib_cache[n] = fib(n-1) + fib(n-2)
> end
> end

```

The following function is a shorter alternative to fib because of its use of  
get!. However, it does not work. I don’t know why **can someone explain why it dosen’t work ?.**

```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

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [April 14, 2020, 11:26pm UTC](https://discourse.julialang.org/t/function-problem/37596/2 "2020-04-14T23:26:11Z")

</div>

Not sure if this is an exercise or you just want it to work. If the latter, you may want to look at the Memoize package, which I described and demonstrated the usage of in a recent StackOverflow answer:

[https://stackoverflow.com/questions/60997656/how-does-this-recursive-function-in-julia-work/60998070#60998070](https://stackoverflow.com/questions/60997656/how-does-this-recursive-function-in-julia-work/60998070#60998070)

Regarding your specific problem, you could write it like this:

```julia
const FIB_CACHE = Dict{BigInt,BigInt}(0 => 0, 1 => 1)

fib(n::Integer) = get!(FIB_CACHE, n) do
    fib(n-1) + fib(n-2)
end

```

```julia
julia> [fib(k) for k = 1:10]
10-element Array{BigInt,1}:
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55

julia> fib(1234)
347746739180370201052517440604335969788684934927843710657352239304121649686845967975636459392453053377493026875020744760145842401792378749321113719919618588095724485583919541019961884523908359133457357334538791778480910430756107407761555218113998374287548487

```

This works, but note that using a dict for `FIB_CACHE` is kind of inefficient: the keys are always going to be value `1:N` where `N` is the largest value you’ve called `fib` on. This is going to fail if `N` is too large to hold in an `Int`, so we can do something else instead which is a bit more complicated but more efficient in term of both memory and compute:

```julia
const FIB_CACHE = BigInt[1, 1]

function fib(n::Integer)
    n < 1 && return big(0)
    n <= length(FIB_CACHE) && return FIB_CACHE[n]
    sizehint!(FIB_CACHE, n)
    r = fib(n-1) + fib(n-2)
    push!(FIB_CACHE, r)
    return r
end

```

This is a bit tricky and relies on a few subtle things:

- we ensure that `FIB_CACHE` is grown to the right size before doing any work by calling `sizehint!` first, which reallocates the array memory if necessary
- then we recursively compute `r` which fills in all the cache entries \< `n`
- these calls never have to reallocate the cache because of the `sizehint!` call
- calling `push!(FIB_CACHE, r)` always puts the value at the right place beacuse the recursive calls have already filled in all the values up to `n-1` by that time

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [April 14, 2020, 11:35pm UTC](https://discourse.julialang.org/t/function-problem/37596/3 "2020-04-14T23:35:10Z")

</div>

This is exactly the same code in [Why is this code not working?](https://discourse.julialang.org/t/why-is-this-code-not-working/37523). Homework problem?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [April 14, 2020, 11:47pm UTC](https://discourse.julialang.org/t/function-problem/37596/4 "2020-04-14T23:47:05Z")

</div>

Just for fun, here’s an iterative version instead which is clearer and more efficient:

```julia
function fib(n::Integer)
    n < 1 && return big(0)
    m = length(FIB_CACHE)
    if m < n
        resize!(FIB_CACHE, n)
        for i = m+1:n
            FIB_CACHE[i] = FIB_CACHE[i-1] + FIB_CACHE[i-2]
        end
    end
    return FIB_CACHE[n]
end

```

---

<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:15am UTC](https://discourse.julialang.org/t/function-problem/37596/5 "2020-04-15T00:15:05Z")

</div>

Thank you for your explanation, Yes this is a part of an Exercise. but actually the problem is when I running this code in Julia

```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

```

i got LoadError: StackOverflowError and it seems that this code in this way dosn’t check whether the Fibonacci number is in the cache and it repeated many time so we got this error but i am not sure this is the only error or not !

---

<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:24am UTC](https://discourse.julialang.org/t/function-problem/37596/6 "2020-04-15T00:24:49Z")

</div>

Did you look at your [classmate’s post](https://discourse.julialang.org/t/why-is-this-code-not-working/37523)? The problem is explained clearly by [Henrique](https://discourse.julialang.org/t/why-is-this-code-not-working/37523/3).

Edit: I see now that you responded to Henrique in that thread. Let’s take it there.

---

<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:27am UTC](https://discourse.julialang.org/t/function-problem/37596/7 "2020-04-15T00:27:15Z")

</div>

Yes , and you can also check my reply to him . the problem is not related to Negative numbers as he explained. the code doesn’t work in general even if for a positive number