How does the fibonacci recursive function “work”?

by

You’re defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). We’re just representing this relationship in code. So, for fibonnaci(7) we can observe:

  • fibonacci(7) is equal to fibonacci(6) + fibonacci(5)
  • fibonacci(6) is equal to fibonacci(5) + fibonacci(4)
  • fibonacci(5) is equal to fibonacci(4) + fibonacci(3)
  • fibonacci(4) is equal to fibonacci(3) + fibonacci(2)
  • fibonacci(3) is equal to fibonacci(2) + fibonacci(1)
  • fibonacci(2) is equal to fibonacci(1) + fibonacci(0)
  • fibonacci(1) is equal to 1
  • fibonacci(0) is equal to 1

We now have all the parts needed to evaluate fibonacci(7), which was our original goal. Notice that the base case — return 1 when n < 2 — is what makes this possible. This is what stops the recursion, so that we can can start the process of unrolling the stack and summing the values we’re returning at each step. Without this step, we’d continue calling fibonacci on smaller and smaller values right up until the program finally crashed.

It might help to add some logging statements that illustrate this:

function fibonacci(n, c) {
    var indent = "";
    for (var i = 0; i < c; i++) {
        indent += " ";
    }
    console.log(indent + "fibonacci(" + n + ")");
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
    }
}

console.log(fibonacci(7, 0));

Output:

fibonacci(7)
    fibonacci(5)
        fibonacci(3)
            fibonacci(1)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
    fibonacci(6)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
        fibonacci(5)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
            fibonacci(4)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
                fibonacci(3)
                    fibonacci(1)
                    fibonacci(2)
                        fibonacci(0)
                        fibonacci(1)

Values at the same level of indentation are summed to produce the result for the previous level of indentation.

More Related Contents:

  1. Way to go from recursion to iteration
  2. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  3. Determining complexity for recursive functions (Big O notation)
  4. Tower of Hanoi: Recursive Algorithm
  5. Prolog Accumulators. Are they really a “different” concept?
  6. What is recursion and when should I use it?
  7. How can I make recursive templates in AngularJS when using nested objects?
  8. Is Cmake set variable recursive?
  9. Recursive function causing a stack overflow
  10. “application: not a procedure” in binary arithmetic procedures
  11. Java recursive Fibonacci sequence
  12. count the number of calls of a clause
  13. recursive variadic template to print out the contents of a parameter pack
  14. Recursion vs loops
  15. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  16. Real-world examples of recursion [closed]
  17. Recursive Fibonacci memoization
  18. I got “scheme application not a procedure” in the last recursive calling of a function
  19. Implications of foldr vs. foldl (or foldl’)
  20. Examples of Recursive functions [closed]
  21. Is it possible to make a recursive closure in Rust?
  22. Fibonacci sequence in Ruby (recursion)
  23. What is the fastest way to write Fibonacci function in Scala?
  24. Why is my recursive function so slow in R?
  25. What does “Overflow evaluating the requirement” mean and how can I fix it?
  26. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
  27. Which recursive functions cannot be rewritten using loops? [duplicate]
  28. Recursive function returning none? [duplicate]
  29. Factorial using Recursion in Java
  30. What is a non recursive solution for Fibonacci-like sequence in Java?

Leave a Comment