Fatorial exponencial resolvido com recursão.

robgeek
(usa Debian)

Enviado em 29/04/2018 - 21:46h

Boa noite!

Queria saber qual o raciocínio por trás do código abaixo. Eu entendi, eu acho, o que ele está fazendo, mas eu nunca teria pensado desse jeito, pois me parece totalmente contra intuitivo.
Problema:


Código que funciona, mas não entendi a lógica:

int fatExp(int n) {

	int interna(int n, int k) {

		if(k == 1) {

			return n;

		}

		return interna(n * interna(n, k - 1), k - 1);

	}

	return interna(n, n - 1);

} 

Código que eu fiz, mas não funciona:

int expoFat(int num) {

	int intern(int n, int p) {

		if(p == 1)	

			return n;

		

		int aux = (n - 1);



		return (n * intern(n, (aux * intern(aux, (p - 1)))));

	}



	return intern(num, (num - 1));

} 

O que eu pensei foi o seguinte:
Se eu passar o número 4, que teria: 4^3^2^1. Para isso, eu, recursivamente formaria essa expressão. Note que eu mantenho o 4 na base, ali no "return (n*... " porque ele deveria ser o último a ser calculado. Bem, não funcionou.

Olhando o código que funciona eu vi que ele já vai multiplicando o 4 várias vezes, mas seguindo um raciocínio estranho. O que me desanima é que funciona, porque eu nunca teria pensado nessa solução.

paulo1205
(usa Ubuntu)

Enviado em 01/05/2018 - 04:33h

Tanto o código que funciona quanto a sua versão se baseiam num recurso proibido pelo C e pelo C++, que é declaração de funções dentro de funções. O GCC aceita esse recurso como extensão, mas mesmo ele para e indica erro quando compilado com opções de diagnóstico voltadas a portabilidade.

$ cat func.c

int fatExp(int n) {

	int interna(int n, int k) {

		if(k == 1)

			return n;

		return interna(n * interna(n, k - 1), k - 1);

	}

	return interna(n, n - 1);

}



$ gcc -pedantic-errors -c func,c

func.c: In function ‘fatExp’:

func.c:2:2: error: ISO C forbids nested functions [-Wpedantic]

  int interna(int n, int k) {

  ^ 

Quanto à diferença de resultados entre a sua versão e a versão que você apresentou como certa (embora viole uma regra do C), ela parece derivar do entendimento de como uma série de exponenciações deve ser interpretada.

Veja que a exponenciação, ao contrário da multiplicação e da adição, não é comutativa. Por exemplo, 2^5 é bem diferente de 5^2. Além disso, a associatividade também não é comutativa. Por exemplo, 2^(5^2)=2^25=33554432, mas (2^5)^2=32^2=1024.

Sem entrar numa análise muito detalhada, parece que você foi por um caminho de que a associatividade de n^(n-1)^(n-2)^...^2^1 ocorreria da direita para a esquerda, numa forma parecida com n^((n-1)^((n-2)^((...^2)^1))) (com possíveis variações, mas o sono desta hora não me permite analisar a fundo), ao passo que a solução “certa” faz associatividade à esquerda ((((n^(n-1))^(n-2))^...)^2)^1.

Veja a diferença entre essas duas expressões com n=4: a primeira vira 4^(3^2), que é 4^9, ao passo que a segunda vira (4^3)^2, que é 4^6.

-----------

Curiosamente, veja que a solução certa é exatamente igual a n^((n-1)!).