Tail recursion and fibonacci

Question

I looked at this site: http://rosettacode.org/wiki/Fibonacci_sequence#JavaScript and saw this program:

function fib(n) { return function(n,a,b) { return n>0 ? arguments.callee(n-1,b,a+b) : a; }(n,0,1); } 

How it works, what are the two arguments (a and b). I followed it and still can’t understand how it works.

Answer 1

In function(n,a,b) , n serves as a countdown counter, and a b stores two consecutive Fibonacci numbers to calculate the next, so when n reaches 0, you have a as the number n + of the 1st Fibonacci number (since real Fibonacci at the beginning has two 1s).

For example, n = 4:

 nab 4 0 1 3 1 2 2 2 3 1 3 5 0 5 8 

As you can see, the value of a and b is always equal to the Fibonacci number. Furthermore, it is very similar to functional programming (as Scheme programmers are listed on the website).

Answer 2

a and b are parameters to the newly defined anonymous function.

I would look at this page , which is the documentation for arguments . From the documentation, arguments.callee is a reference to the function you are currently in. This needs to be done because they work in an anonymous function, so it really doesn't have a name (what they know).

It seems that they recursively call a function that they (anonymously) define to a depth of n . Along the way, they calculate the number of fibs, and they return the value of a after depth n been reached. The initial values ​​passed to the function are (n,0,1)

Answer 3

As explained here , arguments.callee refers to the current function you are in. Since the function you are in is anonymous , this is the only way to call the function and achieve recursion.

A particular function calculates a Fibonacci sequence by recursively calling an internal function.

Answer 4

a and b represent the current sequence number and the next sequence number, starting at 0 and 1 . n is a countdown timer that indicates which element of the fibonacci sequence will be returned (EG: n = 10 will return 55 ).

This function works by taking the argument n , which means that it will calculate the nth sequence number:

 function fib(n) { 

The code then defines a function that will calculate the following number in the sequence:

 function(n,a,b) { return n>0 ? arguments.callee(n-1,b,a+b) : a; } 

Basically, this anonymous function counts n for each time it is executed, while at the same time moving a and b to the next numbers in the sequence. If n is 0 , then the sequence ends and the current number a returned.

arguments.callee refers to the current executable function, so the code simply means to call new arguments into itself. In other words, to start the next iteration of the "loop".

Finally, saying (n,0,1); , the code really calls the parameters n,0,1 in fib . The return , which I missed from the above snippet, takes the return value of the anonymous function and returns it to the caller fib .

---

However, using recursion in this way is inefficient for languages ​​like JavaScript that do not have tail call optimization. For large n you'd better write this using a standard loop construct instead of recursion.

Answer 5

I see several problems that can lead to confusion. Optimization of short arm and tail for a recursive function template.

The problem may be with a short manual version of the code. Rewritten for clarity below.

• Confirmation of an anonymous function by specifying the name "recur"
• conditional (ternary) operator expanded.

Tail optimization is used to manually use the stack with recursive functions by adding part of the battery. This is an ordinary model, but it removes readability. This is the recur function.

It should be especially noted that productivity is great in comparison with repetition in a cycle.

 function fib(n) { function recur(n, a, b) { if (n > 0) { return recur(n - 1, b, a + b); } else { return a; } } return recur(n, 0, 1); } 

As for the parameters, n is the iteration counter, a and b are parts of the fibonacci sequence.