If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Improving efficiency of recursive functions

Recursion can be an elegant way to solve a problem, and many algorithms lend themselves to recursive solutions. However, recursive algorithms can be inefficient in terms of both time and space. We'll explore several techniques to improve their efficiency here.
In the coding challenge to recursively compute the factorial of a number, we asked you to call the function multiple times with different values.
For example, this JavaScript code calls factorial() 4 times:
factorial(0);
factorial(2);
factorial(5);
factorial(10);
Let's consider all the calls that the computer makes when executing those 4 lines of code:
Line of codeRecursive callsTotal calls
factorial(0)1 call
factorial(2)factorial(1)factorial(0)3 calls
factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)6 calls
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)factorial(4)factorial(3)factorial(2)factorial(1)factorial(0)11 calls
Notice that factorial(10) has to make 11 function calls, and 6 of those have the exact same arguments and return values as previous function calls made during factorial(5).

Memoization of factorial

We can use a technique called memoization to save the computer time when making identical function calls. Memoization (a form of caching) remembers the result of a function call with particular inputs in a lookup table (the "memo") and returns that result when the function is called again with the same inputs.
A memoization of the factorial function could look like this:
  • If n = 0, return 1
  • Otherwise if n is in the memo, return the memo's value for n
  • Otherwise,
    • Calculate (n1)!×n
    • Store result in the memo
    • Return result
This algorithm checks for the input value in the memo before making a potentially expensive recursive call. The memo should be a data structure with efficient lookup times, such as a hash table with O(1) lookup time.
If you'd like to visualize the execution of the memoized algorithm implemented in JavaScript, watch this video or run the visualization yourself. Before watching, you may want to challenge yourself to implement the algorithm in the language of your choice.
With memoization implemented, the computer can make fewer total calls over repeated calls to factorial():
Line of codeRecursive callsTotal calls
factorial(0)1 call
factorial(2)factorial(1)factorial(0)3 calls
factorial(5)factorial(4)factorial(3)factorial(2)3 calls
factorial(10)factorial(9)factorial(8)factorial(7)factorial(6)factorial(5)6 calls
Memoization makes a trade-off between time and space. As long as the lookup is efficient and the function is called repeatedly, the computer can save time at the cost of using memory to store the memo.

Memoization of Fibonacci

In the case of the factorial function, an algorithm only benefits from the optimization of memoization when a program makes repeated calls to the function during its execution. In some cases, however, memoization can save time even for a single call to a recursive function.
Let's look at a simple example, the algorithm for generating Fibonacci numbers.
The Fibonacci sequence is a famous series of numbers where the next number in the sequence is the sum of the previous 2 numbers. The first two numbers in the sequence are defined as 0 and 1. After that, the next number is 1 (from 0+1) and the number after that is 2 (from 1+1), and so on.
The first 10 Fibonacci numbers:
0,1,1,2,3,5,8,13,21,34
A simple recursive function for generating the n-th Fibonacci number looks like this:
  • If n is 0 or 1, return n
  • Otherwise, return fibonacci(n1)+fibonacci(n2)
This algorithm is an example of multiple recursion since it calls itself multiple times. To understand the multiple calls that the computer makes, it helps to visualize the calls as a tree.
When n=5, the computer makes 15 calls:
Khan Academy video wrapper
Recursive Fibonacci Calls (Diagrammed)See video transcript
Notice the multiple calls to the fibonacci function for the input values of 3, 2, 1, and 0. As the input gets larger, this gets increasingly inefficient. A call to fibonacci(30) results in the computer calling fibonacci(2) over half a million times.
We can use memoization here to prevent the computer from recomputing a Fibonacci number that it's already computed.
The memoized version of the recursive Fibonacci algorithm looks like this:
  • If n is 0 or 1, return n
  • Otherwise, if n is in the memo, return the memo's value for n
  • Otherwise,
    • Calculate fibonacci(n1)+fibonacci(n2)
    • Store result in memo
    • Return result
If you'd like to visualize the execution of the memoized algorithm implemented in JavaScript, watch this video or run the visualization yourself.
For n=5, the computer makes 9 calls:
Khan Academy video wrapper
Memoized Recursive Fibonacci Calls (Diagrammed)See video transcript
The original version of the algorithm required 15 function calls, so the memoization eliminated 6 function calls.
This table shows the number of calls required for n=5 up to n=10:
nOriginalMemoized
5159
62511
74113
86715
910917
1017719
The total number of function calls increases at an exponential rate for the original algorithm but at a much slower linear rate for the memoized algorithm.
The memoized algorithm does requires more space, however; enough for the memo to store every return value of n.

Bottom-up

Sometimes the best way to improve the efficiency of a recursive algorithm is to not use recursion at all.
In the case of generating Fibonacci numbers, an iterative technique called the bottom-up approach can save us both time and space. When using a bottom-up approach, the computer solves the sub-problems first and uses the partial results to arrive at the final result.
A bottom-up approach to Fibonacci number generation looks like this:
  • If n is 0 or 1, return n
  • Otherwise,
    • Create variable twoBehind to remember the result of (n2) and initialize to 0
    • Create variable oneBehind to remember the result of (n1) and initialize to 1
    • Create variable result to store the final result and initialize to 0
    • Repeat (n1) times:
      • Update result to the sum of twoBehind plus oneBehind
      • Update twoBehind to store the current value of oneBehind
      • Update oneBehind to store the current value of result
      • Return result
This approach never makes a recursive call; it instead uses iteration to sum up the partial results and calculate the number.
If you'd like to visualize the execution of the bottom-up algorithm implemented in JavaScript, watch this video or run the visualization yourself.
The bottom-up algorithm has the same O(n) time complexity as the memoized algorithm but it requires just O(1) space since it only remembers three numbers at a time.

Dynamic programming

Memoization and bottom-up are both techniques from dynamic programming, a problem-solving strategy used in mathematics and computer science.
Dynamic programming can be used when a problem has optimal substructure and overlapping subproblems. Optimal substructure means that the optimal solution to the problem can be created from optimal solutions of its subproblems. In other words, fib(5) can be solved with fib(4) and fib(3). Overlapping subproblems happen whenever a subproblem is solved multiple times, which we saw when fib(5) made multiple calls to the typically recursive fib(3) and fib(2).
Dynamic programming can be used for a range of problems and involves techniques besides the ones we learned here. If you're working on a problem with optimal substructure and overlapping subproblems, consider whether a dynamic programming approach may work.

Want to join the conversation?

  • blobby green style avatar for user Karthikeyan Alagarswamy
    Assuming a fibonacci sequence 0,1,1,2,3,5,8,13,21,34. When I calculate fib(5), I am finding the 5th fibonacci number. In other words, fib(n) means finding n-th fibonacci number. In that case how can the base case have n=0. Because, we are counting the sequence starting 1 and not zero, right?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Martin
      Hmm the Fibonacci sequence starts with

      fib(0)= 0 and fib(1) = 1

      and from there its
       
      fib(n) = fib(n-1) + fib(n-2)

      So you'll start with the base cases 0 and 1 and work your way from up there.
      [The starting point of the natural numbers isn't always clear, sometimes people include 0 sometimes not]
      (5 votes)
  • blobby green style avatar for user Đặng Gia Chí
    I'm a little confused about the table showing the number of calls of the func factorial when using memoization. The factorial(11) should use only 5 calls, right? If I'm wrong can you show me which calls are the 6 calls please. Thanks in advanced:)
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Not sure where you're seeing factorial(11). The table has factorial(10). However, it is inconsistent as to whether the last function (for the memoized value) is being counted.

      Anyway, it's really not worth worrying about a difference of 1 or 2 function calls as these will vary with the specific implementation of the algorithm.

      The thing to focus on is that memoizing can save a lot of function calls. In the case of the recursive factorial, it can save a linear number of function calls, and in the case of Fibonacci numbers it can save an exponential number of function calls.
      (4 votes)
  • leaf blue style avatar for user Miki  Munna
    how does "The memoized version of the recursive Fibonacci algorithm" causes fib(n) to call 5 times when n=5?
    PLEASE EXPLAIN.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      fib(5)-> fib(4) + fib(3)
      fib(4)-> fib(3) + fib(2)
      fib(3)-> fib(2) + fib(1)
      fib(2)-> fib(1) + fib(0)

      All the terms on the left hand side result in calls to fib(x) i.e. for fib(4),fib(3),fib(2),fib(1).
      fib(0) also results in a call to fib(0).
      5 calls
      For all the lines, but the last, by the time we process the terms on the right, they have already been memoized and we don't need to call fib(x) because we have already stored the result.
      (5 votes)
  • blobby green style avatar for user mickey171904
    How to create multiple recursion without having maximum call stack size exceeded error?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Every time you call a function it must save the current state of variables on the stack. Since memory is limited, and the memory allocated to the stack is even more limited, you will eventually run out of memory if the recursion depth (the amount of times you call the function without returning) is too large. So, you can avoid stack overflow by increasing the size of stack memory (more RAM dedicated to the stack), or by not using recursion on problems which would require a large recursion depth.

      Stack overflow errors also often occur in programs that don't reach their base case and return. This is similar to an infinite loop in an iterative program.

      The good news is, every recursive solution has an iterative equivalent. So, one can convert their recursive solution to an iterative solution. In fact, some programming languages will automatically convert simple tail recursion to iterative versions. Unfortunately, more complex recursive solutions can be hard to convert. One general technique is to save only the necessary info (as opposed to the state of all the variables) for the solution onto stacks stored in heap memory (as opposed to stack memory), which usually has more room (but is still finite).

      Hope this makes sense
      (3 votes)
  • purple pi purple style avatar for user Kaitlyn
    Do factorials affect dynamic programming?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Martin
      Dynamic programming is a way of solving problems, in which store values that you previously calculated.
      The reason they talk about factorials here is that this is a problem that is very suitable to be solved with dynamic programming, because otherwise you'll have to do the same operation over and over again.
      Say you want to calculate fib(6)

      fib(6)= fib(5) + fib(4)
      = fib(4) + fib(3) + fib(3) + fib(2)
      = fib(3) + fib(2) + fib(2) + fib(1) +
      fib(2) + fib(1) + fib(1)
      = fib(2) + fib(1) + fib(1) +
      fib(1) + 1 + fib(1) + 1 +1
      = fib(1) + fib(1) + 1 + 1 + 1 + 1 +
      1 + 1
      = 8

      As you can see the calculating fib numbers is really messy even for a relative small n, but if you store every fib(n) that you calculate you save yourself a lot of repeat calculations. IN the example you could you could calculate fib(3) and fib(2) once store the values and then use them when you need them.


      But aside from that dynamic programming doesn't really have anything to do with factorials.
      (5 votes)
  • blobby green style avatar for user Highdee
    Here's a more efficient way of calculating Fibonacci numbers using dynamic programming
    function fibonacci(x) {
    let first = 0;
    let second = 1;
    let sum = 0;
    for (let i = 2; i <= x; i++) {
    sum = first + second;
    first = second;
    second = sum;
    }
    return sum;
    }
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Philipp Klein
    Under 'Memoization of factorial' the table should show 4 calls in the total calls column for factorial(5) not 3, I believe.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user khaledkunbargi
    Does anybody know a good source to learn memoization in c++?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Memoization is basically the same in every programming language, but here is an a Fibonnaci example in C++
      #include <iostream>
      #include <map>
      using namespace std;

      map<long,long> stored_results;

      long fib(long n ){

      cout << "Called fib("
      << n
      << ")"
      << endl;

      long result;

      //check to see if we already
      //have calculated fib(n)
      //by checking the map with
      //stored results
      map<long,long>::iterator memoized_value =
      stored_results.find(n);
      if (memoized_value != stored_results.end() ){
      result = memoized_value->second;
      cout << "used stored result: fib("
      << n << ")="
      << result
      <<endl;
      return result;
      }

      //we didn't find it in the map,
      //so we have to calculate it
      if( n == 0){
      result = 0;
      }
      else if( n == 1){
      result = 1;
      }
      else {
      result = fib(n-1) + fib(n-2);
      }

      //store the result (memoize it),
      //so we can reuse it
      stored_results[n] = result;
      cout << "calculated fib("
      << n
      << ")="
      << result
      << endl;
      return result;

      }

      int main() {
      long fib_query = 10;
      long myresult = fib(fib_query);
      cout << "Final result fib("
      << fib_query
      << ")="
      << myresult
      << endl;
      return 0;
      }
      (1 vote)