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?

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]

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:)

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.

How to create multiple recursion without having maximum call stack size exceeded error?

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

Do factorials affect dynamic programming?

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.

how does "The memoized version of the recursive Fibonacci algorithm" causes fib(n) to call 5 times when n=5? PLEASE EXPLAIN.

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.

Main content

Improving efficiency of recursive functions

Google Classroom

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 code	Recursive calls	Total 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 left parenthesis, n, minus, 1, right parenthesis, !, times, 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, left parenthesis, 1, right parenthesis 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 code	Recursive calls	Total 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, plus, 1) and the number after that is 2 (from 1, plus, 1), and so on.

The first 10 Fibonacci numbers:

0, comma, 1, comma, 1, comma, 2, comma, 3, comma, 5, comma, 8, comma, 13, comma, 21, comma, 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 start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis

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, equals, 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 start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis
- 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, equals, 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, equals, 5 up to n, equals, 10:

n	Original	Memoized
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

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 start text, t, w, o, B, e, h, i, n, d, end text to remember the result of left parenthesis, n, minus, 2, right parenthesis and initialize to 0
- Create variable start text, o, n, e, B, e, h, i, n, d, end text to remember the result of left parenthesis, n, minus, 1, right parenthesis and initialize to 1
- Create variable start text, r, e, s, u, l, t, end text to store the final result and initialize to 0
- Repeat left parenthesis, n, minus, 1, right parenthesis times:
  - Update start text, r, e, s, u, l, t, end text to the sum of start text, t, w, o, B, e, h, i, n, d, end text plus start text, o, n, e, B, e, h, i, n, d, end text
  - Update start text, t, w, o, B, e, h, i, n, d, end text to store the current value of start text, o, n, e, B, e, h, i, n, d, end text
  - Update start text, o, n, e, B, e, h, i, n, d, end text to store the current value of start text, r, e, s, u, l, t, end text
  - Return start text, r, e, s, u, l, t, end text

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, left parenthesis, n, right parenthesis time complexity as the memoized algorithm but it requires just O, left parenthesis, 1, right parenthesis 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.

[Attribution]

Want to join the conversation?

Sort by:

Karthikeyan Alagarswamy
Posted 3 years ago. Direct link to Karthikeyan Alagarswamy's post “Assuming a fibonacci sequ...”
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?
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- Martin
  Posted 3 years ago. Direct link to Martin's post “Hmm the Fibonacci sequenc...”
  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]
  Comment on Martin's post “Hmm the Fibonacci sequenc...”
  (3 votes)
Đặng Gia Chí
Posted 2 years ago. Direct link to Đặng Gia Chí's post “I'm a little confused abo...”
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:)
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- Cameron
  Posted 2 years ago. Direct link to Cameron's post “Not sure where you're see...”
  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.
  Comment on Cameron's post “Not sure where you're see...”
  (3 votes)
mickey171904
Posted 2 years ago. Direct link to mickey171904's post “How to create multiple re...”
How to create multiple recursion without having maximum call stack size exceeded error?
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- Cameron
  Posted 2 years ago. Direct link to Cameron's post “Every time you call a fun...”
  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
  Button navigates to signup page
  (2 votes)
Kaitlyn
Posted 3 years ago. Direct link to Kaitlyn's post “Do factorials affect dyna...”
Do factorials affect dynamic programming?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Martin
  Posted 3 years ago. Direct link to Martin's post “Dynamic programming is a ...”
  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.
  Button navigates to signup page
  (4 votes)
Miki Munna
Posted 3 years ago. Direct link to Miki Munna's post “how does "The memoized ve...”
how does "The memoized version of the recursive Fibonacci algorithm" causes fib(n) to call 5 times when n=5?
PLEASE EXPLAIN.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Cameron
  Posted 3 years ago. Direct link to Cameron's post “fib(5)-> fib(4) + fib(3) ...”
  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.
  Comment on Cameron's post “fib(5)-> fib(4) + fib(3) ...”
  (3 votes)
Philipp Klein
Posted 2 years ago. Direct link to Philipp Klein's post “Under 'Memoization of fac...”
Under 'Memoization of factorial' the table should show 4 calls in the total calls column for factorial(5) not 3, I believe.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer

khaledkunbargi

Posted 5 months ago. Direct link to khaledkunbargi's post “Does anybody know a good ...”

Does anybody know a good source to learn memoization in c++?

Button navigates to signup pageButton navigates to signup page

(1 vote)

Cameron

Posted 5 months ago. Direct link to Cameron's post “Memoization is basically ...”

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;
}

Button navigates to signup page

(0 votes)

Computer science

Course: Computer science > Unit 1