Main content

## Computer science

### Unit 1: Lesson 6

Recursive algorithms- Recursion
- The factorial function
- Challenge: Iterative factorial
- Recursive factorial
- Challenge: Recursive factorial
- Properties of recursive algorithms
- Using recursion to determine whether a word is a palindrome
- Challenge: is a string a palindrome?
- Computing powers of a number
- Challenge: Recursive powers
- Multiple recursion with the Sierpinski gasket
- Improving efficiency of recursive functions
- Project: Recursive art

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

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

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:

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:

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.

## Want to join the conversation?

- 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?(2 votes)
- 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](3 votes)

- 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:)(2 votes)
- 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.(3 votes)

- How to create multiple recursion without having maximum call stack size exceeded error?(2 votes)
- 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(2 votes)

- Do factorials affect dynamic programming?(1 vote)
- 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.(4 votes)

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

PLEASE EXPLAIN.(1 vote)- 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.(3 votes)

- Under 'Memoization of factorial' the table should show 4 calls in the total calls column for factorial(5) not 3, I believe.(1 vote)
- Does anybody know a good source to learn memoization in c++?(1 vote)
- 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;

}(0 votes)