Complexidade e funções recursivas

> Tutorial LeekScript

Aviso: Este artigo é matematicamente intensivo (pelo menos para este wiki). Não use sem orientação médica.

Falando sério: aqui vou tentar falar sobre a Optimization das funções recursivas (The_Recursion). Este artigo é mais para pessoas interessadas em programação funcional e teoria da programação.

Nem sempre é fácil, ao escrever uma função recursiva, saber quantas chamadas faremos antes de chegar ao resultado. Ou mesmo se chegaremos ao resultado, às vezes. O tutorial em La_Récursivité oferece maneiras de otimizar funções recursivas, mas não estuda complexidade ou correção; Vou, portanto, ilustrar aqui com exemplos alguns métodos para se orientar.

Esta lista de exemplos não pretende ser exaustiva, será necessário que cada um de seus algoritmos examine precisamente as operações realizadas.

Cabe a você copiar essas ideias para seus algoritmos pessoais e, se encontrar outros exemplos dignos de menção, explique-os aqui!

Primeiros exemplos

Algumas funções recursivas simples têm complexidade fácil de estudar. Este é o caso do primeiro exemplo do tutorial sobre recursão:

função somaN(n){ if (n === 0) { return 0; } else { return n + somaN(n - 1); } }

Aqui, é bem simples: podemos ver facilmente que se dermos um inteiro n (positivo!) a essa função, ela adicionará n à soma de 0 a n-1, que calcula chamando a si mesma de par. Então vamos fazer n + (n-1 + ... + (0)...), que faz n adições e n chamadas de função, ou seja, uma complexidade de O( n).

No entanto, se dermos um inteiro negativo como entrada, esta função causará um estouro de pilha: adicionará números negativos sem nunca chegar a 0. Da mesma forma, se dermos um número não inteiro, nunca chegaremos a 0 subtraindo 1 várias vezes . Portanto, preste atenção à '''correção''' de suas funções recursivas: se você não previu todos os casos ou se os utiliza com uma entrada que não corresponde ao que você tinha em mente ao codificá-la, você pode ter surpresas desagradáveis.

O tutorial de otimização fornece um exemplo de função de complexidade O(2^n):

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

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

var sub_lista = subArray(lista_itens, 1, nb_itens - 1); var parcial_combos_lista = getAllCombos(sub_lista); // chamada recursiva var m = count(list_combos_partial);

//Em seguida, duplicamos a lista de combos: mantemos os que tínhamos e adicionamos os mesmos com o primeiro elemento de liste_items for(var i=0; i P(n) = 2*P(n-1). Como também temos P(1) = 2, obtemos a fórmula P(n) = 2 * ... * 2 = 2^n, daí o (em menos) complexidade exponencial. Podemos então mostrar que esta função tem uma complexidade exponencial (e não maior): cada chamada para a função cria um array de tamanho n-1 com subArray (custo: O(n )), então m pushs com m o tamanho da matriz de combinação parcial, ou seja, 2^(n-1) (custo: K * 2^(n-1) com K o push cost), que esmaga o custo do subArray e, portanto, leva a uma complexidade determinada pelo número P(n) de pushes executados.

É essa ideia que vou desenvolver aqui: obter uma fórmula de recorrência e tentar deduzir uma fórmula para aumentar o número de chamadas, para finalmente deduzir a complexidade estudando o que a função faz além de suas chamadas recursivas. Não vou mais falar muito sobre correção (exceto no final), mas mantenha a noção em mente...

A seguir, C(n) denotará o custo da função estudada.

Recorrências simples: C(n) = f(C(n-1))

A palavra "simples" aqui não significa que o complexo