Estrutura de dados - Noções básicas de recursão

Algumas linguagens de programação de computador permitem que um módulo ou função chame a si mesmo. Essa técnica é conhecida como recursão. Em recursão, uma funçãoα chama a si mesmo diretamente ou chama uma função β que por sua vez chama a função original α. A funçãoα é chamada de função recursiva.

Example - uma função que chama a si mesma.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - uma função que chama outra função que por sua vez a chama novamente.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Propriedades

Uma função recursiva pode ser infinita como um loop. Para evitar a execução infinita de função recursiva, existem duas propriedades que uma função recursiva deve ter -

Base criteria - Deve haver pelo menos um critério ou condição base, de modo que, quando essa condição for atendida, a função pare de chamar a si mesma recursivamente.
Progressive approach - As chamadas recursivas devem progredir de forma que cada vez que for feita uma chamada recursiva se aproxime dos critérios básicos.

Implementação

Muitas linguagens de programação implementam recursão por meio de stacks. Geralmente, sempre que uma função (caller) chama outra função (callee) ou ela própria como receptor, a função do chamador transfere o controle de execução para o receptor. Esse processo de transferência também pode envolver alguns dados a serem passados do chamador para o receptor.

Isso implica que a função do chamador deve suspender sua execução temporariamente e retomar mais tarde, quando o controle de execução retornar da função do receptor. Aqui, a função do chamador precisa começar exatamente do ponto de execução onde ela se coloca em espera. Ele também precisa dos mesmos valores de dados exatos nos quais estava trabalhando. Para isso, um registro de ativação (ou stack frame) é criado para a função do chamador.

Este registro de ativação mantém as informações sobre variáveis locais, parâmetros formais, endereço de retorno e todas as informações passadas para a função do chamador.

Análise de recursão

Pode-se argumentar por que usar recursão, já que a mesma tarefa pode ser feita com iteração. A primeira razão é que a recursão torna um programa mais legível e, por causa dos mais recentes sistemas aprimorados de CPU, a recursão é mais eficiente do que as iterações.

Complexidade de tempo

No caso de iterações, consideramos o número de iterações para contar a complexidade do tempo. Da mesma forma, em caso de recursão, assumindo que tudo é constante, tentamos descobrir o número de vezes que uma chamada recursiva está sendo feita. Uma chamada feita para uma função é Ο (1), portanto, o (n) número de vezes que uma chamada recursiva é feita torna a função recursiva Ο (n).

Complexidade do Espaço

A complexidade do espaço é contabilizada como a quantidade de espaço extra necessária para a execução de um módulo. No caso de iterações, o compilador dificilmente requer qualquer espaço extra. O compilador continua atualizando os valores das variáveis usadas nas iterações. Mas em caso de recursão, o sistema precisa armazenar o registro de ativação cada vez que uma chamada recursiva é feita. Assim, considera-se que a complexidade espacial da função recursiva pode ser maior do que a de uma função com iteração.