I will not give an example of code, it suffices to recall the calculation of the n-th member of the Fibonacci series: F (n) = F (n-1) + F (n-2). And what is worth reading to know the answer to such questions?

  • four
    In this particular case, simple common sense is sufficient. For example, decompose F (n-1) again and see the problem (the same values ​​are calculated a hundred times). And in the linear version, you calculate each value only once. In general, recursion is another function call (and so several times)) but it is not free and costs more than a cycle - BOPOH
  • one
    @BOPOH I think you can easily convert your comment into a reply. - andreycha
  • @BOPOH I gave the first example that came to mind. Is it necessary to avoid the use of recursion in all cases? - Side
  • @Side recursion and unchangeable types in capable hands is a complete good. read a good book on functional programming - even if you don’t use it in practice, some of the things you’ve previously avoided — recursion, immutable types, extensions, higher order functions — will be unexpectedly useful to you. You will start to see beautiful solutions, where you would have written a simple canvas of code before :) - PashaPash ♦
  • one
    @avp, I ran into this in a python under Windows, when I increased the permissible limit of recursion. At #python they said - if you need to increase the limit, then something you are doing wrong. In particular, the recursion should be changed to an iteration - BOPOH

2 answers 2

The cost of calling a function in languages ​​that support tail call optimization (for example, any .net platform language — C #, F #, C ++ CLI) is almost the same as a normal loop. And even if this optimization cannot be applied - the call to a non-virtual function is usually quite cheap.

Therefore, recursive algorithms operate at the same speed as their linear counterparts . If "analogs" is used in the literal sense, then recursion is a way of organizing code.

Specifically, in the case of Fib you usually implement two different algorithms:

  • in linear, you calculate the values ​​of the terms of the sequence once.
  • recursively, you most likely calculate F (of a particular x) several times.

This discrepancy is removed using a technique called memoization (caching the results of the F (x) call). Because Fib is a pure function (it depends only on its arguments), then the result of its execution is easily cached:

Here is a variant that will calculate the value of Fib (x) each time - slow

 let rec fibs n = if n < 1 then 1 else (fibs (n - 1)) + (fibs (n - 2))

Here is an option that will calculate the Fib (x) value only once for each x:

 let rec fibs = memoize (fun n -> if n < 1 then 1 else (fibs (n - 1)) + (fibs (n - 2)))

where memoize is:

 open System.Collections.Generic /// The function creates a function that calls the argument 'f' /// only once and stores the result in a mutable dictionary (cache) /// Repeated calls to the resulting function return cached values. let memoize f = // Create (mutable) cache that is used for storing results of // for function arguments that were already calculated. let cache = new Dictionary<_, _>() (fun x -> // The returned function first performs a cache lookup let succ, v = cache.TryGetValue(x) if succ then v else // If value was not found, calculate & cache it let v = f(x) cache.Add(x, v) v)

By the way, Fib is such a typical example for memoization, that it is shown on the Wiki Haskel in the Memoization with recursion section , and the implementation of memoization is several times shorter than on F #:

 memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)

As RAVON recalled, not any recursion can be optimized through the tail call. For example, the fibs solution on F # above is not subject to this optimization. The solution and support for this optimization looks like this:

 let fib n = let rec loop acc1 acc2 = function | n when n = 0I -> acc1 | n -> loop acc2 (acc1 + acc2) (n - 1I) loop 0I 1I n

In essence, this is the same loop — a function that calls itself n times, passing to itself the last two terms of the sequence, but written in recursive form. Something like this is implemented inside Seq.unfold , which allows to generate sequences in which the next element depends on the previous ones.

  • Not all languages ​​support tail recursion; for example, a python (maybe in new versions is, but hard to believe) And if memory serves, in compiled languages, tail recursion at the compilation stage unfolds into a cycle, so there is no difference. But after all, not every recursion can be turned into a tail (or am I mistaken?), Which means there will be little confusion from this optimization in this case and the recursion can already be compared with the cycle - BOPOH
  • @BOPOH not every, and support in different ways. for example, .net includes this optimization at the jit-compilation stage. therefore, there is a reservation at the beginning of the answer. Yes, not every recursion can be turned into a tail. but still, the challenge of a non-virtual function is a very cheap thing. By the way, the example from the answer is not subject to tail call optimization. - PashaPash ♦
  • The @BOPOH question is more like "what to read," and not "how quickly to calculate Fibonacci." so I tried to wrap the topicaster in functionalism. because the correct answer is "a good OP book." - PashaPash ♦
  • one
    @BOPOH 1. Yes, not all languages ​​can do something with tail recursion. 2. When writing code, any recursive function can be rewritten to use tail recursion. But not every recursive function has tail recursion and can be optimized accordingly. - Qwertiy ♦
  • @Qwertiy, and bypassing the tree, for example, how can you remake the use of tail recursion? I just can not immediately come up with an option. - BOPOH

You compare wrong. You must compare an iterative algorithm with a similar recursive algorithm:

 (Fib(1), Fib(0)) = (1, 1) (Fib(n+1), Fib(n)) = (Fib(n) + Fib(n-1), Fib(n))

which leads to code

 (int, int) CalcFibHelper(int fcurr, int fprev, int n) { if (n == 0) return (fcurr, fprev); return CalcFib(fcurr + fprev, fcurr, n-1); } int CalcFib(int n) { (int result, int prev) = CalcFibHelper(1, 1, n); return result; }

A compiler that can work well with tail recursion can convert recursive code to iterative code. The preference and speed of various implementations of the algorithm depends on the compiler: F #, for example, knows how to work with recursive algorithms better, and C # with iterative ones.