Will many parameters in a recursive function cause performance issues?

Question

My code will traverse around in a binary tree in a recursive fashion. Doing this I have some parameters I need to control. Thus, my function looks like this:

FindPoints(int leftchild, int rightchild, int ly_index, int uy_index, int bit, int nodepos, int amount, int level);

It is called a lot of times. Will the performance of my program take a hit because of the amount of parameters?

Answer 1

The process during recursion is:

1. Allocate space for parameters on the stack. Usually subtracting a value from the stack pointer register.
2. Copy variable values onto the stack. Depends on the objects or values.
3. Call function. This may cause a flush of the processor's instruction cache.
4. At end of function, stack pointer is restored by adding a value.
5. Return from function call; may cause flush to instruction cache.

The general concern is not performance, but recursion depth and stack size. Recursion that goes beyond the limitations of the stack is called a Stack Overflow defect.

An iterative solution may be faster because the compiler may be able to optimize the loop. Optimizing recursive calls is more difficult for a compiler to optimize.

By the way, on modern processors, the worst case timing of a recursive call is less than 1 millisecond, usually around nanosecond resolution. So you are trying to squeeze nanoseconds out of a program. Not very good Return On Investment (ROI).

Answer 2

Performance depends on many factors; ideally you would try one way, try the other and compare. However, here are some general considerations that may help you get a feel of what is going on:

• If your function does much work, time wasted on function calls will not be significant.
• If your function mostly passes parameters unchanged, you should definitely think about refactoring your code. If it calls itself with all (or almost all) parameters having different values, you cannot improve your code - it's too complex.
• Function call performance depends on calling convention. Compilers typically pass the first few parameters in registers (very fast), and the rest on stack (slower). You might want to make the number of parameters small (2 for fastcall; 4 for ARM convention - just two examples that I know), such that they all fit into registers.

To expand on second point - if your function doesn't change most of its parameters, each call will copy these parameters around the stack - this is absolutely useless work for the computer. In addition to wasting time, it also wastes space in data cache (leading to more slowdown, which is particularly nasty because it cannot even be attributed to any code in particular) and might cause stack overflow (or maybe not, depending on your OS).

One way to improve your code in this situation is: using a struct that holds all unchanged parameters, and passing a pointer/reference to it:

struct DataForFindPoints
{
    int ly_index;
    int uy_index;
    int bit;
    int nodepos;
    int amount;
    int level;
};

FindPoints(int leftchild, int rightchild, const DataForFindPoints& data);

Or (object-oriented way): make a class that has FindPoints as a member function, and all unchanged parameters as fields.