Complexity and recursive functions

> LeekScript Tutorial

Warning: This article is mathematically intensive (at least for this wiki). Do not use without medical advice.

More seriously: here I am going to try to talk about the Optimization of recursive functions (The_Recursion). This article is more for people who are interested in functional programming and programming theory.

It is not always easy, when writing a recursive function, to know how many calls we will make before arriving at the result. Or even if we will arrive at the result, sometimes. The tutorial on La_Récursivité gives ways to optimize recursive functions, but does not study complexity or correction; I will therefore illustrate here with examples some methods to find your way around.

This list of examples is not intended to be exhaustive, it will be necessary for each of your algorithms to examine precisely the operations carried out.

Then it's up to you to copy these ideas for your personal algorithms, and if you find other examples worth mentioning, explain them here!

First examples

Some simple recursive functions have easy-to-study complexity. This is the case of the first example of the tutorial on recursion:

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

Here, it's quite simple: we can easily see that if we give an integer n (positive!) to this function, it will add n to the sum from 0 to n-1, which it calculates by calling itself- same. So we are going to do n + (n-1 + ... + (0)...), which makes n additions and n function calls, i.e. a complexity of O( n).

However, if we give a negative integer as input, this function will cause a stack overflow: it will add negative numbers without ever reaching 0. Similarly, if we give a non-integer number, we will never reach 0 by subtracting 1 several times. So pay attention to the '''correction''' of your recursive functions: if you have not foreseen all the cases or if you use them with an input that does not correspond to what you had in mind when coding it, you could have unpleasant surprises.

The optimization tutorial gives an example of a O(2^n) complexity function:

function getAllCombos(list_items){ var nb_items = count(list_items);

if(nb_items == 1) { return [[], list_items]; }

var sub_list = subArray(list_items, 1, nb_items - 1); var partial_combos_list = getAllCombos(sub_list); // Recursive call var m = count(list_combos_partial);

//We then duplicate the list of combos: we keep the ones we had, and we add the same ones with the first element of liste_items for(var i=0; i P(n) = 2*P(n-1). As we also have P(1) = 2, we obtain the formula P(n) = 2 * ... * 2 = 2^n, hence the (at least) exponential complexity. We can then show that this function has an exponential complexity (and no greater): each call to the function creates an array of size n-1 with subArray (cost: O(n )), then does m pushes with m the size of the partial combo array, i.e. 2^(n-1) (cost: K * 2^(n-1) with K the push cost), which crushes the cost of the subArray, and thus leads to a complexity determined by the number P(n) of pushes performed.

It is this idea that I will develop here: obtain a recurrence formula and try to deduce a formula to increase the number of calls, to finally deduce the complexity by studying what the function does in addition to its calls recursive. I won't talk so much about correction anymore (except at the very end), but keep the notion in mind...

In the following, C(n) will designate the cost of the function studied.

Simple recurrences: C(n) = f(C(n-1))

The word "simple" here does not mean that the complexi