Just a question about recursive functions, no code.

[carl123]

What are different ways of ensuring efficiency in a recursive function? i.e. Prevent calling your recursive function when not necessary.

[Computergeek01]

Prevent calling your recursive function when not necessary.

Easy, you test for the break condition before you call it. Calling the function without evaluating the break condition doesn't make the slightest bit of sense. Consider:

This

#include <iostream>
#include <string>

int loop(int& num)
{
    num++;
    
    if(num != 10)
    {
        loop(num);
    }
    
    return num;
}

int main()
{
    int Num = 0;
    
    loop(Num);
    
    std::cout << "NUM: " << Num << "\n";
}

Verses this

#include <iostream>
#include <string>

void loop(int& num)
{
    num++;
    
    loop(num);
    
    if(num == 10) return;
}

int main()
{
    int Num = 0;
    
    loop(Num);
    
    std::cout << "NUM: " << Num << "\n";
}

Hint, one of these doesn't accomplish the task.

[dhayden]

One way to prevent recursive calls is to try to partition the problem cleanly. For example if you call f(N), then it's better if you can recursively call f(N/2) rather than f(N-1). If you call f(N-1) then you run the risk of N calls to f.

You can (and should) be careful with amount of local storage that you allocate in each recursive call. Otherwise you risk overflowing the stack.

You can try to make the function non-recursive. Sometimes you can convert the recursion into a loop. Sometimes you can put the new arguments at the end (or beginning) of a list and just have the program process the list. A recursive sort algorithm might use this technique.

But if your goal is simply to make your recursive function efficient, then that's a question of choosing the right algorithm and/or data structure for the problem. While both are important, I think I can say that most inefficient code I've seen was the result of choosing the wrong data structure, rather than the wrong algorithm. I don't mean a huge majority, but maybe 2/3.