1
$\begingroup$

In an older question I asked about stack, the statement came up that recursive functions cannot be inlined (link). I am interested in whether this statement is actually true or not. I understand that it is extremely impractical. But, is it impossible, in theory? To my intuition, it seems like it should be possible. But I might lack the ability to imagine recursive functions that cannot be inlined.

I am in no way an expert. I am just curious. I like to understand constraints.

The recursive factorial function for a factorial like this:

int factorial(int n) {
    if(n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

Can for example be inlined as below. Each return value is stored in its own integer. The max depth here is 4, but can be increased arbitrarily at the cost of program size (in some way analogous to how the cost for recursive functions with subroutines is the stack size. ) Extremely impractical, but, I am just interested in: is it impossible, or possible.

int factorial_inlined(int n) {
    if(n > 1) {
        int n1;
        if((n-1) > 1) {
            int n2;
            if((n-2) > 1) {
                int n3;
                if((n-3) > 1) {
                    int n4;
                    if((n-4) > 1) {
                        n4 = 1; // Inlining max depth reached
                    }
                    else {
                        n4 = 1;
                    }
                    n3 = (n-3)*n4;
                }
                else {
                    n3 = 1;
                }
                n2 = (n-2)*n3;
            }
            else {
                n2 = 1;
            }
            n1 = (n-1)*n2;
        }
        else {
            n1 = 1;
        }
        return n*n1;
    }
    else
        return 1;
}

int main() {
  cout << factorial_inlined(4) << endl;
  return 0;
}

I am also able to inline Towers of Hanoi to a depth of two (it has no return values though) and my intuition is that it can be arbitrarily increased to any depth (at the cost of program size. )

void hanoi(int n, char src, char dst, char aux) {
    if (n == 0) {
        // base case: do nothing
    } else if (n == 1) {
        // base case: move top disk from src to dst
        cout << "Move disk from " << src << " to " << dst << endl;
    } else {
        // recursive case:
        // move top n-1 disks from src to aux
        if (n-1 == 0) {
            // base case: do nothing
        } else if (n-1 == 1) {
            // base case: move top disk from src to aux
            cout << "Move disk from " << src << " to " << aux << endl;
        } else {
            // recursive case:
            // move top n-2 disks from src to dst
            if (n-2 == 0) {
                // base case: do nothing
            } else if (n-2 == 1) {
                // base case: move top disk from src to dst
                cout << "Move disk from " << src << " to " << dst << endl;
            } else {
                // recursive case: do nothing
            }
            // move remaining disk from src to aux
            cout << "Move disk from " << src << " to " << aux << endl;
            // move top n-2 disks from dst to aux
            if (n-2 == 0) {
                // base case: do nothing
            } else if (n-2 == 1) {
                // base case: move top disk from dst to aux
                cout << "Move disk from " << dst << " to " << aux << endl;
            } else {
                // recursive case: do nothing
            }
        }
        // move remaining disk from src to dst
        cout << "Move disk from " << src << " to " << dst << endl;
        // move top n-1 disks from aux to dst
        if (n-1 == 0) {
            // base case: do nothing
        } else if (n-1 == 1) {
            // base case: move top disk from aux to dst
            cout << "Move disk from " << aux << " to " << dst << endl;
        } else {
            // recursive case: do nothing
        }
    }
}

int main() {
hanoi(2, 'A', 'C', 'B');
return 0;
}

Edit: To clarify in response to answer that mentioned the inlined Factorial could not do n = 10, yes it was inlined to a max depth of 4. To inline it to a max depth of 11 (supporting n = 10 and also n = 11) it can just be expanded as below. The cost in program size for this, is in some way analogous to the cost in stack size (a larger stack is needed for deeper recursive calls, or it will overflow. )

int factorial_inlined(int n) {
    if(n > 1) {
        int n1;
        if((n-1) > 1) {
            int n2;
            if((n-2) > 1) {
                int n3;
                if((n-3) > 1) {
                    int n4;
                    if((n-4) > 1) {
                        int n5;
                        if((n-5) > 1) {
                            int n6;
                            if((n-6) > 1) {
                                int n7;
                                if((n-7) > 1) {
                                    int n8;
                                    if((n-8) > 1) {
                                        int n9;
                                        if((n-9) > 1) {
                                            int n10;
                                            if((n-10) > 1) {
                                                int n11;
                                                if((n-11) > 1) {
                                                    n11 = 1; // Inlining max depth reached
                                                }
                                                else {
                                                    n11 = 1;
                                                }
                                                n10 = (n-10)*n11;
                                            }
                                            else {
                                                n10 = 1;
                                            }
                                            n9 = (n-9)*n10;
                                        }
                                        else {
                                            n9 = 1;
                                        }
                                        n8 = (n-8)*n9;
                                    }
                                    else {
                                        n8 = 1;
                                    }
                                    n7 = (n-7)*n8;
                                }
                                else {
                                    n7 = 1;
                                }
                                n6 = (n-6)*n7;
                            }
                            else {
                                n6 = 1;
                            }
                            n5 = (n-5)*n6;
                        }
                        else {
                            n5 = 1;
                        }
                        n4 = (n-4)*n5;
                    }
                    else {
                        n4 = 1;
                    }
                    n3 = (n-3)*n4;
                }
                else {
                    n3 = 1;
                }
                n2 = (n-2)*n3;
            }
            else {
                n2 = 1;
            }
            n1 = (n-1)*n2;
        }
        else {
            n1 = 1;
        }
        return n*n1;
    }
    else
        return 1;
}

int main() {
  cout << factorial_inlined(11) << endl;
  return 0;
}
$\endgroup$
14
  • $\begingroup$ You show yourself that this is possible, so why asking ? It is even thinkable that a compiler could "unroll" the first levels of a recursion the same way it can unroll a loop. $\endgroup$
    – user16034
    Dec 28, 2022 at 12:14
  • $\begingroup$ Because you stated it was not. And I show it is possible for a very small number of cases. That are extremely simple recursive functions. Recursive functions, subroutines, stack, is pretty new to me. I do not assume I would be able to imagine all cases. So, that is why I asked, exactly. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 23:21
  • $\begingroup$ Before asking here, I had a long discussion with OpenAI about it, to cover the basics of it :) tinyurl.com/inliningrecursion. I just dislike to learn wrong. So I wanted to see if your statement was true, or not. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 23:25
  • 1
    $\begingroup$ I don't think the point is that it uses "a lot of program memory". The point is that you have to decide before you do the inlining what the limit of memory is going to be. With recursive calls using a stack, you do not have to make that decision before you know which instance of the problem you're going to solve. Exactly the same program, without modification, will work for any problem provided that it is run on a machine with sufficient stack space. (Or, theoretically, you could migrate the execution from a machine without enough stack to another machine with more stack, as necessary.) $\endgroup$
    – rici
    Dec 29, 2022 at 17:35
  • 1
    $\begingroup$ In this sense, you can "inline" a recursive function in exactly the same way as you can "unroll" a loop; that is, you can hard-code a portion of the iteration, but in order to be able to solve an arbitrarily large computation, you need some mechanism to continue after the hard-coded prefix is done. And that mechanism is still a loop (or still a recursion.) ... If you might consider that an answer to your question, I'm happy to contribute it as an answer. $\endgroup$
    – rici
    Dec 29, 2022 at 17:41

3 Answers 3

3
$\begingroup$

I think you're conflating two different problems here.

One is "inlining" (the elimination of a method call), the other is "loop unrolling" (the elimination of a jump instruction).

Certainly, recursive method calls can always be replaced with a loop and a stack, and therefore a recursive method can be inlined by transforming it into a loop with a stack.

And loops which operate for a fixed number of iterations can always be unrolled.

$\endgroup$
7
  • $\begingroup$ Thanks for answer! I don't know if I conflate any problems. I had seen the statement "recursive functions cannot be inlined" and it seemed false. But since I am humble that I might not know everything about recursive functions, I wanted to ask. I would count loops as inlining too, but if the function can also be written without a loop that is even less close to making it impossible to inline. Overall, I have yet to see why it would be impossible to write recursive function without subroutines and stack, it is just extremely impractical. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 23:19
  • 1
    $\begingroup$ @BipedalJoe, it's certainly possible to transform certain kinds of recursive calls into loops without a stack (if the only recursion is tail recursion), or even into a sequence of instructions with no loop or stack (if the only recursion is tail recursion, and the recursion is of a fixed depth), but in the general case there must be a loop and a stack because that is essentially what a recursive call is (the repeated pushing and popping of values on a stack). $\endgroup$
    – Steve
    Dec 29, 2022 at 1:13
  • $\begingroup$ What I really want to know is if there are examples where it is impossible. The argument that the recursion has to be of finite depth, can't the program just make sure to inline sufficient depth to cover the equivalent of what the stack (depending on its size) could cover? It would use up and waste huge amounts of memory but it does not seem impossible, at all. I am very open to that there could be examples of recursive functions that cannot be inlined (those incl. function pointers are an example but that is due to the nature of function pointers, not the recursion) but I am not aware of any. $\endgroup$
    – BipedalJoe
    Dec 29, 2022 at 8:22
  • 1
    $\begingroup$ @BipedalJoe, let's go back one step again. Are you talking about inlining, or are you talking about unrolling? Inlining does not mean unrolling. Also, they do not apply to the same things. Inlining is something you can do to methods/subroutines (or subexpressions, in relevant languages). Unrolling is something you do to looping constructs. (1/2) $\endgroup$
    – Steve
    Dec 29, 2022 at 10:14
  • $\begingroup$ You cannot unroll to cover the same depth as a stack can cover, because the algorithm using a stack is a more compact representation, so for any given amount of system memory (which is the implicit limit on both the stack, and on the unrolled instructions), the unrolled version would hit the memory limit long before the stack version. (2/2) $\endgroup$
    – Steve
    Dec 29, 2022 at 10:17
2
$\begingroup$

Your inlined factorial function is incorrect. When $n=10$ (for instance), it gives the wrong result. This is not considered a correct way of inlining. The implicit requirement, when inlining is that the code must maintain the same behavior.

Of course, if you don't require that the code produce the same result in all cases, it is trivial to do such an inlining. For instance, you could just replace the factorial function with "return 42". But this is rather silly and useless.

As far as whether you can inline a recursive function, not in the straightforward way. But there are ways to inline it while maintaining correct behavior. For instance, if it is tail-recursive, as in the factorial function, you can replace the entire function with a loop. More generally, you can replace the recursive implementation with an iterative implementation that uses an explicit stack, and then inline that.

So, in general, yes, it is always possible to replace the code of the function in such a way that it can be inlined, while always producing the same result from the computation. Whether you consider that useful in practice or the kind of answer you were looking for is up to you.

$\endgroup$
5
  • $\begingroup$ Hi, I'm just interested in understanding. The inlining of course needs to cover the max depth needed. It's comparable to how the stack has to be larger for more depth in recursive functions. The factorial is easily increased to any arbitrary max depth, I added n = 11 to the question to show that but I think you and anyone else here also already knows that. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 8:40
  • $\begingroup$ Tail recursion can be done with loops, yeah that's basic and well known. And they can also be inlined in a similar way to the factorial example I used. But I'm interested specifically about if recursive functions inlining, in general, is either possible or impossible. And mostly (since it proves that point) if there are examples of when it would be impossible. What I considered useful is verifying if the statement I linked to was true, or not (its useful to not learn wrong, makes it easier... ) Wouldn't ever practically inline recursive functions myself, just want to know the constraints. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 8:46
  • $\begingroup$ Your updated version still gives wrong results for, for example, n = 10000. $\endgroup$ Dec 28, 2022 at 9:31
  • $\begingroup$ Yes and in that case you would need to have inlined with max depth covering n = 10000. That's clearly described in the question, in my answer to D.W., and common sense. And comparable to how stack size has to increase as n increases, as well. I do not think it means inlining recursive functions is impossible. I am open to that there may be recursive functions that cannot be inlined but I'm not yet aware of any. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 10:21
  • $\begingroup$ @BipedalJoe Check out tail recursion. $\endgroup$
    – Pål GD
    Dec 28, 2022 at 14:36
2
$\begingroup$

It is usually up to the compiler what exactly to do, and an "inline" command is just a hint. Inlining is usually a trade between call overhead and the amount of code, and the compiler is in the best position to decide. In addition, the compiler may be able to optimise the code because it knows the parameters at call time, so factorial(5) might be turned into 120. For trivial functions, calling them could be more code than inlining, so the decision is easy. For the factorial function, it's not.

I'd expect the compiler to recognise recursion, directly or indirectly, so it doesn't inline forever. It can just refuse inlining. In case of the factorial function, analysis by a human and the assumption that n is usually not small (0, 1 or 2) shows that one level of inlining in the function itself saves half the calls. I'll write a slightly different call for readability. Original:

return n <= 1 ? 1 : n * factorial(n-1)

Inlining one level:

return n <= 1 ? 1 : n * (n - 1 <= 1 ? 1 : (n-1) * factorial(n-2)

Simplify:

return n <= 1 ? 1 : n * (n <= 2 ? 1 : (n-1) * factorial(n-2)

Optimise:

return n <= 1 ? 1 : n <= 2 ? n : n * ((n-1) * factorial(n-2))

This saves half the calls, with little extra code. Now the compiler needs to realise that at some time it needs to stop inlining. As an intelligent human I know that another level of inlining reduces the calls from 1/2 to 1/3, so much less benefit, and ten levels of inlining is pointless. For a compiler that could be a compiler setting, or the compiler author having a clever algorithm to stop at the right time.

From experience, I did an experiment with an inlined fibonacci function, and the compiler got very, very slow with fib(20) and crashed with fib(26).

Note that in this case inlining is most effective if you only inline calls within the function itself - if a random other function calls "factorial" then inlining at the caller site has very little positive effect.

$\endgroup$
2
  • $\begingroup$ I don't mean using the "inline command", I mean in theory. If you were to do it yourself, manually, in assembly, for example. $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 23:17
  • $\begingroup$ (I call "explicitly writing out subroutines back into each place they were called from" inlining. Maybe not right use of word, I saw someone else use it so I called it that too. So not about the command "inline". ) $\endgroup$
    – BipedalJoe
    Dec 28, 2022 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.