CODEWITHSUNDEEP
c++recursionprogramming-languagesinlinecomputer-science
Tim
Tim

Reputation: 99526

How to use inline with recursion?

From Programming Language Pragmatics, by Scott, regarding in-lining and recursion:

In-line expansion is also not an option in the general case for recursive subroutines. For the occasional case in which a recursive call is possible but unlikely, it may be desirable to generate a true recursive subroutine, but to expand one level of that routine in-line at each call site.

As a simple example, consider a binary tree whose leaves contain character strings. A routine to return the fringe of this tree (the left-to-right concatenation of the values in its leaves) might look like this in C++:

string fringe(bin_tree *t) {
    // assume both children are nil or neither is
    if (t->left == 0) return t->val;
    return fringe(t->left) + fringe(t->right);
}

A compiler can expand this code in-line if it makes each nested invocation a true subroutine call. Since half the nodes in a binary tree are leaves, this expansion will eliminate half the dynamic calls at run time.

If we expand not only the root calls but also (one level of) the two calls within the true subroutine version, only a quarter of the original dynamic calls will remain.

I am having trouble understanding the following sentences:

What do they mean actually? Could you explain them with the given example, for example, show what the code is like after taking the action of each sentence?

Thanks.

Upvotes: 2

Views: 516

Answers (3)

eerorika
eerorika

Reputation: 238421

Could you explain them with the given example, for example, show what the code is like

Note: The compiler/optimizer does not do the these actions on the C++ code that you write, but on some internal representation. It is possible to demonstrate the idea with C++, but due to syntax and readability issues, we may need to introduce additional changes such as temporary variables.

expand one level of that routine in-line at each call site.

result = fringe(t);

becomes

if (t->left == 0) result = t->val;
else result = fringe(t->left) + fringe(t->right);

expand not only the root calls but also (one level of) the two calls within the true subroutine version

if (t->left == 0) result = t->val;
else {
    string left, right;

    // one level of expansion for left subtree
    if (t->left->left == 0) left = t->left->val;
    else left = fringe(t->left->left) + fringe(t->left->right);

    // one level of expansion for right subtree
    if (t->right->left == 0) right = t->right->val;
    else right = fringe(t->right->left) + fringe(t->right->right);

    result = left + right;
}

Upvotes: 1

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Some compilers can expand and inline quite nested recursive calls.

For example the following code (where I did not use the inline keyword!):

static int fact(int n) {
    if (n<=1) return 1;
    else return n* fact(n-1);
}

extern "C" int f5();
int f5() {
    return fact(5);
}

is compiled (using g++ -O2 -fverbose-asm -S) by GCC 7.2 (On Linux/Debian/Sid on x86-64) into a simple function returning 120:

         .text
         .p2align 4,,15
         .globl  f5
         .type   f5, @function
 f5:
 .LFB1:
         .cfi_startproc
 # e.cc:10: };
         movl    $120, %eax      #,
         ret
         .cfi_endproc
 .LFE1:
         .size   f5, .-f5
         .ident  "GCC: (Debian 7.2.0-1) 7.2.0"
         .section        .note.GNU-stack,"",@progbits

Notice that fact has been entirely inlined and do not appear in the generated assembler code.

"expand one level of that routine in-line at each call site"

That would mean that f5 would have been compiled into the equivalent of

int f5() { return 5*fact(4); }

with fact appearing in the generated code and compiled into a recursive (machine code) function (consuming the call stack).

Upvotes: 1

MSalters
MSalters

Reputation: 180010

By far the easiest way to understand this, is to think of inlining as creating an alternative binary representation. E.g. besides creating the basic string fringe(bin_tree *t), the compiler may also decide to create string fringe__inlined(bin_tree *t). And in fringe__inlined, the actual inlined function(s) will be one or two copies of fringe.

It would even be possible to create a fringe__inlined__inlined this way (two levels, as mentioned).

Upvotes: 1

Related Questions