When does a recursive algorithm provide better performance than an iterative one?

Can someone give an example of a case when a recursive algorithm is faster than any iterative algorithm?

Consider the Knapsack problem - here the recurrence is:

f(weight, index, val) = val // i >= n
f(weight, index, val) = f(weight, index+1, val)  // w[i] > W
f(weight, index, val) = max( f(weight, index+1, val), f(weight-weights[i], index+1, val+values[i]) ) // otherwise

Top down DP (memoization) computes only the necessary states in the search space to arrive at the solution. Bottom up on the other hand computes all the states.

So for recurrences with variable values in the search space, Top Down will only compute the necessary states instead of all of them so theoretically depending on your input, top down could search for significantly fewer states.

/r/learnprogramming Thread