1

I want to know the details about the execution of recursive functions.

#include<iostream>
int a=0;
int fac(int n) {
    if (n <= 1)
        return n;
    int temp = fac(n-2) + fac(n - 1);
    a++;
    return temp;
}
int main() {
    fac(4);
    std::cout<<a;
}

The output is 4.

I want to know when int temp = fac(n-2) + fac(n - 1)； is executed, for example fac(4-2)+fac(4-1) ---> fac(2)+fac(3), at this time, compiler will finish fac(2) first? or finish it together? I'm not good at English, I hope that there is no obstacle to your reading.

AndyLi
  • 81
  • 3
  • 1
    I assume your code is missing a global `int a` – Tas Jun 18 '19 at 04:33
  • Andy, please make sure the code your post compiles. Your question might want to read "How can I create a trace which shows the call order where there is recursion?" – Keith Jun 18 '19 at 04:37
  • 1
    C++ is a compiled language, so there is no "translator" which executes code. The compiler converts everything to machine code making an executable, which can then be executed. Compilation and execution are completely separate processes. – eesiraed Jun 18 '19 at 04:38
  • What's `fac_1`? Please post the real code which actually compiles. – eesiraed Jun 18 '19 at 04:40
  • I check basically, print something at every recursive functions. for example in your code, i add `printf("fac(%d) is called\n", n);` at the start of function. – Zem Jun 18 '19 at 04:42
  • The order of evaluation of the two operands in operators like `+` is undefined. This means the C++ standard does not dictate which recursive call will happen first, so they can happen in any order. – eesiraed Jun 18 '19 at 04:43
  • thinks your advices ,This is my first time using this website.I made some mistakes,please forgive me. – AndyLi Jun 18 '19 at 04:45
  • "*The output is 1.*" - No, it outputs `4`. – melpomene Jun 18 '19 at 04:49
  • This is part of the code, I implemented another function, I have been confused, I modified the problem, thank you for reminding. I will write a piece of code separately next time. – AndyLi Jun 18 '19 at 05:01

2 Answers2

1

Analysing this code purely in an algorithmic sense with no respect to C++ implementation intricacies,

                   fac(4)
      fac(2)         +            fac(3)
       |----------------------------|
fac(0) + fac(1)              fac(1) + fac(2)
  1    +   1                    1   + fac(0) + fac(1)
                                    +   1    +   1

How can I create a trace which shows the call order where there is recursion?

First, I want to make note that the compiler output produced by the compiler will not match one-to-one with the code you write. The compiler applies different levels of optimization based on the flags provided to it with the highest level being -O3 and the default being -O0 but those seem out of scope of this question. Creating a trace influences this process itself as the compiler now needs to meet your expectations of what the trace looks like. The only true way to trace the actual execution flow is to read the assembly produced by the compiler.

Knowing that, we can apply a trace to see the call order by printing to screen when execution enters the called method. Note, I have removed a as it does not really trace anything and only adds to the complexity of the explanation.

int fac(int n) {
    std::cout << "fac(" << n << ")" << std::endl;
    if (n <= 1)
        return n;
    int temp = fac(n-2) + fac(n - 1);
    return temp;
}

int main() {
    fac(4);
}

// Output

fac(4)
fac(2)
fac(0)
fac(1)
fac(3)
fac(1)
fac(2)
fac(0)
fac(1)

As seen by this output on my PC, execution has proceeded from left to right depth first. We can number our call tree with this order to obtain a better picture,

// Call order

                    1. fac(4)
      2. fac(2)         +         5. fac(3)
          |----------------------------|
3. fac(0) + 4. fac(1)        6. fac(1) + 7. fac(2)
                                       + 8. fac(0) + 9. fac(1)

Note: This does not mean that the results will be the same on every implementation nor does it mean that the order of execution is preserved when you remove the trace and allow compiler optimisations but it demonstrates how recursion works in computer programming.

Avin Kavish
  • 8,317
  • 1
  • 21
  • 36
0

First fac(2) will be finished and then fac(1). The output is 4.

The call stack would be like this (from bottom to top) -

                                |---fac(1)
                    |--- fac(2) |
       |---- fac(3) |           |---fac(0)
       |            |
       |            |----fac(1)
       |
fac(4) |
       |
       |            |---- fac(1)
       |---- fac(2) |
                    |---- fac(0)

fac() function will be returned when n <= 1

Faruk Hossain
  • 1,205
  • 5
  • 12
  • Order of evaluation is undefined in C++, so it's perfectly possible that `fact(1)` will be computed first. – eesiraed Jun 18 '19 at 04:59
  • It will be computed by Last-In-First-Out (LIFO, stack) after going to base base case. – Faruk Hossain Jun 18 '19 at 05:04
  • I'm talking about the evaluation order in `int temp = fac(n-2) + fac(n - 1);`. `fac(n - 1)` could be evaluated before `fac(n-2)`. – eesiraed Jun 18 '19 at 05:05
  • No. *fac(n-2)* will be executed first and then *fact(n-1)* – Faruk Hossain Jun 18 '19 at 05:08
  • 1
    Even if operator evaluation is undefined this still highlights how recursive calls work which is OP's question. There's no point obsessing over the order of the + operator the only difference that makes is invert the nodes in this call tree – Avin Kavish Jun 18 '19 at 05:11
  • 1
    You're going to have to back a claim like that with a good documentation source, Faruk. [Here's mine.](https://en.cppreference.com/w/cpp/language/eval_order) – user4581301 Jun 18 '19 at 05:11
  • 1
    @AvinKavish has the right of it though. Since the behaviour of the program will be unaffected, it doesn't matter which happens first. – user4581301 Jun 18 '19 at 05:12
  • @AvinKavish True, I just don't want the OP or anyone else seeing this to think that evaluation always happens left-to-right, since there are situations where this does matter. – eesiraed Jun 18 '19 at 05:15
  • 1
    For all we know, there IS no call tree. The compiler could look the code over, compute the final result, and generate code for `std::cout<<4;` – user4581301 Jun 18 '19 at 05:16
  • 1
    From https://en.cppreference.com/w/cpp/language/eval_order (emphasis mine): "**Except where noted below, there is no concept of left-to-right or right-to-left evaluation in C++.** This is not to be confused with left-to-right and right-to-left associativity of operators: the expression f1() + f2() + f3() is parsed as (f1() + f2()) + f3() due to left-to-right associativity of operator+, but **the function call to f3 may be evaluated first, last, or between f1() or f2() at run time.**" None of the rules state the left operand of the `+` operator has to be evaluated before the right – eesiraed Jun 18 '19 at 05:20
  • 1
    Yeah I looked at the assembly this produces with -O3, there was no recursion it just unrolls fac(4). But I fear we might be overwhelming OP with these advanced discussions. – Avin Kavish Jun 18 '19 at 05:20
  • 1
    This one isn't all that advanced. It's just something teachers and books don't cover all that well. [Lightness Races in Orbit made a great post touching on this recently.](https://stackoverflow.com/a/56553360/4581301) – user4581301 Jun 18 '19 at 05:30
  • But this has no relation to answering OP's question, don't worry about it I'm writing an answer – Avin Kavish Jun 18 '19 at 05:32
  • I have been confused before, when can execute a++, you mean fac(4)---> fac(3) and fac(4) and then execute a++, fac(3)--->fac (2) and fac(1), and then execute a++ again. My confusion is that “int temp=...” will always execute until fac(1) and fac(0) get the result of temp before executing a++. @AvinKavish – AndyLi Jun 18 '19 at 06:00
  • a++ is a bit tricky here because you have a return statement that returns before `a++` is hit on some recursions. – Avin Kavish Jun 18 '19 at 06:03
  • So, in fact, that's what I don'tunderstand.As you said,finally,temp=fac(0)*2+fac(1)*2,When we have finished temp，then a++,so a may jus be 1,that's wrong，i know. so,When to execute a++?@AvinKavish – AndyLi Jun 23 '19 at 12:21