CODEWITHSUNDEEP
algorithmrecursioncomplexity-theory
Asleepace
Asleepace

Reputation: 3745

Interesting recursive function

The other day I was playing around with some recursive functions, and I made a simple algorithm like this:

int f(int n) {
    if (n == 0) return 1;
    return f(f(n-1)-1) * n;
}

What is interesting is that it works for f(0), f(1), f(2), f(3) & f(4) but not matter what language or compiler I try it in, nothing seems to be able to complete f(5) without causing a stack overflow.

My question is how / where could I run this to find the solution to f(5) and also what might be the big-O complexity of a function like this?

The first couple results are 1,1,2,3,8...

Upvotes: 3

Views: 494

Answers (1)

trincot
trincot

Reputation: 350147

The problem with this function is that it does not guarantee the recursion will stop. It would be OK if the argument passed to the recursive call of f would be smaller than n (and >= 0), but for n >= 4, this is no longer the case. f(4) = 8, and so when calculating f(5), you make a recursive call of f with argument f(4)-1, which is 7. So where you had n = 5, now you call it with n = 7, which is not reducing the problem, but making it bigger. This just explodes further: for determining f(7), you need f(6), and for f(6) you need f(5), but that is the value we are looking for, so this is like running in circles for ever and ever.

For this reason, f(5) is undefined. The recursive form cannot be reduced to solve f, so f is not correctly defined.

Upvotes: 5

Related Questions