Why recursion is more efficient sometimes?

Question

I'm learning about optimization, and I saw some problems where recursion gives the best solution - for example, finding the exit in a maze with backtracking.

Why calling the function within itself is more efficient than writing a different but similar function to the similar problem - or just calling it outside itself with the same parameters?

For example, when I made a pseudocode for the maze solving algorithm, I found a way to put the second call outside the function.

Answer 1

If I've understood your example correctly this is not a genuine example of a recursive algorithm. Since the function only calls itself at most once I don't think there can be much efficiency impact. You are basically right that a different function could be used, or the same function called twice. This might have been done to (slightly) reduce the length of the code by avoiding repetition.

In my personal opinion 'tricks' like that are counter-productive as they reduce readability.

If you are interested in the real gains (and drawbacks of recursion) you should look at some code where recursion is really used to solve the same problem for reduced cases. A good example is binary search, which can be done iteratively or recursively. There are many other sorting and searching algorithms that you can probably find implementations of.

Answer 2

Generally it depends on processor characteristics like branching prediction and cache size.

For e.g.: If your solving algorithm size is greater than the processor cache size, the CPU must retrieve pieces of code from main memory or L2 cache which is a slower operation.