Como converter uma função recursiva em uma não recursiva em C

Programação
#1

Boa tarde,

estou com duvidas referente a essa função recursiva.
int f(int i)
{
if (i > 1)
{
return i + f(i-1);
}

else
{
    return 1;
}

}

Gostaria de saber como implementar ela para uma função não recursiva, tem como? Sou novo no ramo de recursividade, alguém poderia me explicar como devo proceder?

seria a criação de uma nova função?

#2

Recursividade nada mais é do que uma função chamar a si mesmo.

Essa função pode sim ser reescrita sem usar recursividade.

Basta entender o que ela faz para então criar um laço de repetição com o mesmo comportamento.

A seguinte função por exemplo:

int f(int i) {
    if (i > 1) {
        return i + f(i - 1);
    } else {
        return 1;
    }
}

Pode ser reescrita dessa forma:

int f(int i) {
    int result = 1;
    while (i > 1) {
        result = result + i;
        i = i - 1;
    }
    return result;
}

Ou de forma mais reduzida:

int f(int i) {
    int result = 1;
    while (i > 1) {
        result += i--;
    }
    return result;
}
2 curtidas
#3

Tem 2 formas de implementar esse tipo de coisa, recursivamente ou iterativamente. Quando se elimina recursão, o que tu faz é converter isso em um método iterativo, ou seja que vai executando um mesmo código dentro de um laço, em lugar de chamando a si mesmo.

Sempre tem.

A forma mais trivial é usar uma estrutura de dados de pilha para simular o comportamento da recursividade usando iteração.

No caso em questão a função pode ser transformada em uma função com recursão de cauda, e por isso pode ser transformada em uma função iterativa sem precisar de uma pilha.

O código

int f(int i)
{
  if (i > 1)
  {
    return i + f(i-1);
  }
  else
  {
    return 1;
  }
}

é equivalente a

int f(int i)
{
  if (!(i > 1))
  {
    return 1;
  }
  else
  {
    return i + f(i-1);
  }
}

agora você precisa transformar em recursão em cauda, pra isso tem que tirar o i + da frente da chamada a f(i - 1):

int f(int i, int acumulador)
{ 
    	if (!(i > 1))
    	{
			return acumulador + 1;
    	}
    	else
    	{
        	return f(i-1, acumulador + i);
    	}
}

dai simplesmente adiciona um laço ao redor do corpo da função:

int f(int i, int acumulador)
{ 
	while (true) {
    	if (!(i > 1))
    	{
    		return acumulador + 1;
    	}
    	else
    	{
        	return f(i-1, acumulador + i);
    	}
	}
}

depois tu torna a chamada recursiva em atualização dos parâmetros, lembrando de atualizar o acumulador antes do i já que ele tem que usar a versão atual, não a nova de i:

int f_iter(int i, int acumulador)
{ 
	while (true) {
    	if (!(i > 1))
    	{
			return acumulador + 1;
    	}
    	else
    	{
    		acumulador = acumulador + i;
    		i = i - 1;
    	}
	}
}

dai dá pra tirar o acumulador já que não há mais recursão, melhorar o estilo do código, etc.

#4

Muito Obrigado pela excelente explicação.

#5

Muito Obrigado pela explicação, tirou muitas dúvidas minhas.