Como determino o tempo de execução de uma função recursiva dupla?

Dada qualquer função arbitrariamente dupla recursiva, como calcular o tempo de execução?

Por exemplo (em pseudocódigo):

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

Ou algo nesse sentido.

Quais métodos poderiam ou deveriam ser usados ​​para determinar algo assim?

Você continua mudando sua função. Mas continue escolhendo aqueles que durarão para sempre sem conversão.

A recursão fica complicada, rápida. O primeiro passo para analisar uma função duplamente recursiva proposta é tentar rastreá-la em alguns valores de amostra, para ver o que ela faz. Se o seu cálculo entrar em um loop infinito, a função não está bem definida. Se o seu cálculo entrar em uma espiral que continua aumentando em números (o que acontece com muita facilidade), provavelmente não está bem definido.

Se o rastreamento fornecer uma resposta, tente criar algum padrão ou relação de recorrência entre as respostas. Depois de ter isso, você pode tentar descobrir seu tempo de execução. Descobrir isso pode ser muito, muito complicado, mas temos resultados como o teorema do mestre que nos permitem descobrir a resposta em muitos casos.

Lembre-se de que, mesmo com uma recursão única, é fácil criar funções cujo tempo de execução não sabemos calcular. Por exemplo, considere o seguinte:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

É atualmente desconhecido se esta função é sempre bem definida, muito menos o seu tempo de execução é.

O tempo de execução desse par específico de funções é infinito, porque nenhum retorna sem chamar o outro. O valor de retorno aé sempre dependente do valor de retorno de uma chamada para bque sempre chama a... e isso é o que é conhecido como recursão infinita .

O método óbvio é executar a função e medir quanto tempo leva. No entanto, isso indica apenas quanto tempo leva para uma entrada específica. E se você não sabe de antemão que a função termina, é difícil: não há uma maneira mecânica de descobrir se a função termina - esse é o problema da parada e é indecidível.

Encontrar o tempo de execução de uma função é igualmente indecidível, pelo teorema de Rice . De fato, o teorema de Rice mostra que mesmo decidir se uma função é executada no O(f(n))tempo é indecidível.

Portanto, o melhor que você pode fazer em geral é usar sua inteligência humana (que, até onde sabemos, não está vinculada aos limites das máquinas de Turing) e tentar reconhecer um padrão ou inventar um padrão. Uma maneira típica de analisar o tempo de execução de uma função é transformar a definição recursiva da função em uma equação recursiva em seu tempo de execução (ou um conjunto de equações para funções recursivas mutuamente):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

Qual o proximo? Agora você tem um problema de matemática: você precisa resolver essas equações funcionais. Uma abordagem que muitas vezes funciona é transformar essas equações sobre as funções inteiros em equações sobre funções analíticas e uso de cálculo para resolver estes, interpretando as funções T_ae T_bcomo funções geradoras .

Ao gerar funções e outros tópicos discretos de matemática, recomendo o livro Concrete Mathematics , de Ronald Graham, Donald Knuth e Oren Patashnik.

Como outros apontaram, analisar a recursão pode ficar muito difícil muito rapidamente. Aqui está outro exemplo disso: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences , é difícil calcular uma resposta e um tempo de execução para elas. Isso ocorre devido a essas funções recursivas mutuamente terem uma "forma difícil".

De qualquer forma, vejamos este exemplo fácil:

http://pramode.net/clojure/2010/05/08/clojure-trampoline/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Vamos começar tentando calcular funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

O tempo de execução é:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Agora vamos escolher outro exemplo um pouco mais complicado:

Inspirado em http://planetmath.org/encyclopedia/MutualRecursion.html , que é uma boa leitura por si só, vejamos: "" "Os números de Fibonacci podem ser interpretados por recursão mútua: F (0) = 1 e G (0 ) = 1, com F (n + 1) = F (n) + G (n) e G (n + 1) = F (n). "" "

Então, qual é o tempo de execução de F? Vamos para o outro lado.
Bem, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Agora R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Não é difícil ver que R (F (m)) = F (m) - por exemplo, o número de chamadas de função necessárias para calcular um número de Fibonacci no índice i é igual ao valor de um número de Fibonacci no índice i. Isso pressupunha que a adição de dois números fosse muito mais rápida que uma chamada de função. Se não fosse esse o caso, isso seria verdade: R (F (1)) = R (F (0)) + 1 + R (G (0)), e a análise disso seria mais complicada, possivelmente sem uma solução fácil de forma fechada.

A forma fechada para a sequência de Fibonacci não é necessariamente fácil de reinventar, sem mencionar alguns exemplos mais complicados.

A primeira coisa a fazer é mostrar que as funções que você definiu terminam e para quais valores exatamente. No exemplo que você definiu

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

bsó termina y <= -5porque, se você inserir qualquer outro valor, terá um termo no formulário b(a(y-1)). Se você expandir um pouco mais, verá que um termo do formulário b(a(y-1))eventualmente leva ao termo b(1010)que leva a um termo b(a(1009))que novamente leva ao termo b(1010). Isso significa que você não pode conectar nenhum valor aque não seja satisfatório x <= -4porque, se você terminar com um loop infinito, em que o valor a ser calculado depende do valor a ser calculado. Então, essencialmente, este exemplo tem tempo de execução constante.

Portanto, a resposta simples é que não há método geral para determinar o tempo de execução das funções recursivas, porque não há procedimento geral que determine se uma função definida recursivamente termina.

Tempo de execução como no Big-O?

Isso é fácil: O (N) - assumindo que há uma condição de terminação.

A recursão é apenas um loop, e um loop simples é O (N), não importa quantas coisas você faça nesse loop (e chamar outro método é apenas mais uma etapa do loop).

O que seria interessante é se você tiver um loop dentro de um ou mais dos métodos recursivos. Nesse caso, você acabaria com algum tipo de desempenho exponencial (multiplicando por O (N) em cada passagem pelo método).