# recurrence(f(x)) find recurrence relation of f(x);

recurrence(a_+b_) := recurrence(a,x)+recurrence(b,x);
recurrence(a_*b_) := If(isfree(a,x), a*recurrence(b,x));

recurrence(mittag(a_,b_,x_)) := mittag(a,b-a,x)/x-1/gamma(b-a)/x;

recurrence(x_!) := x*(x-1)!;
recurrence(gamma(x_)) := x*gamma(x-1);
recurrence(harmonic(x_)) := harmonic(x-1)+1/x;
recurrence(harmonic(x_,r_)) := if(isfree(r,x),harmonic(x-1,r)+1/x^r);

recurrence(psi(x_)) := psi(x-1)+1/x;
recurrence(fibonacci(x_)) := fibonacci(x-1)+fibonacci(x-2);
recurrence(sin(x_)) := sin(x-1)+sin(1/2)*cos(x+1/2)/2;
recurrence(cos(x_)) := cos(x-1)-sin(1/2)*sin(x+1/2)/2;
recurrence(tan(x_)) := tan(x-1)+sin(1)/cos(x+1)/cos(x);
recurrence(cot(x_)) := cot(x-1)-sin(1)/sin(x+1)/sin(x);
recurrence(exp(x_)) := e*exp(x-1);

recurrence(x_^n_) := If(n>1, (x-1)^n-sum((-1)^k*combination(n,k)*x^(n-k),k,1,n,1));
recurrence(a_^x_) := If(isfree(a,x),a*a^(x-1));
recurrence(e^x_) := e*e^(x-1);