How does this recursive function in Julia work?

user_13201741 0
Viewed 199

This code in Julia:

function seq(n)
       if n<2
           return BigInt(2)
       else
           return 1/(3-seq(n-1))
       end
   end

# and then run
[seq(n) for n=1:10]

replicates the recursive sequence Un = 1/(3-U(n-1)) where U1=2 and it works. But can someone explain to me how it works? for every n does it calculate every term before it or does the "return" store it somewhere which it can then call again when it needs to so it doesn't have to calculate every term for n every time?

julia sequence function
1 Answers

It's just a normal recursive function: it calls itself however many times it needs to in order to compute the result. It terminates because every call chain eventually reaches the base case. There is no implicit caching of results or anything like that—it recomputes the same result however many times the function is called. If you want to remember previously calculated values, you can use the Memoize package to automatically "memoize" return values. Here's a terser version of the unmemoized function:

julia> seq(n) = n < 2 ? BigFloat(2) : 1/(3-seq(n-1))
seq (generic function with 1 method)

julia> seq(1) # trigger compilation
2.0

julia> @time [seq(n) for n=1:100];
  0.001152 seconds (20.00 k allocations: 1.069 MiB)

julia> @time [seq(n) for n=1:100];
  0.001365 seconds (20.00 k allocations: 1.069 MiB)

I changed it to fit on a single line and to return BigFloat(2) instead of BigInt(2) since the function returns BigFloat for larger inputs because of the division operation. Note that the second timing is no faster than the first (slower, in fact, probably because garbage collection kicks in during the second but not the first). Here's the same thing but with memoization:

julia> using Memoize

julia> @memoize seqm(n) = n < 2 ? BigFloat(2) : 1/(3-seqm(n-1))
seqm (generic function with 1 method)

julia> seqm(1) # trigger compilation
2.0

julia> @time [seqm(n) for n=1:100];
  0.000071 seconds (799 allocations: 36.750 KiB)

julia> @time [seqm(n) for n=1:100];
  0.000011 seconds (201 allocations: 4.000 KiB)

The first timing is significantly faster than the unmemoized version even though the memoization cache is empty at the start because the same computation is done many times and memoization avoids doing it all but the first time. The second timing is even faster because now all 100 computed values are already cached and can just be returned.

user_6592480
Related