How does this code work? The result doesnt make sense to me and doesnt appear in the debugger-CodePudding

    #include <iostream>

using namespace std;

int f(int n, int m){
    if (n==1)
        return 0;
    else
        return f(n-1, m)   m;
}

int main()
{

cout << f(3874, 1000);
cout << endl;
    return 0;
}

The result is 3873000. Why is n multiplied by m after deducting 1 and how does the function work in detail please?

CodePudding user response：

The else block is executed at all levels of recursion, except the deepest one.

The number of levels in the recursion tree is n. So we have n-1 times that the else block is executed.

This else block first makes the recursive call, and then adds m to the result it gets back, and returns that sum to the caller, who will do the same, ...etc until the walk upwards the recursion tree is complete.

The original caller will thus see a base number (0) to which m was repeatedly added, exactly n-1 times.

So the function calculates m(n-1), provided that n is greater than 0. If not, the recursion will run into a stack overflow error.

Visualisation

To visualise this, let's split the second return statement into two parts, where first the result of the recursive call is stored in a variable, and then the sum is returned. Also, let's take a small value for n, like 3.

So this is then the code:

int f(int n, int m){
    if (n==1)
        return 0;
    else {
        int result = f(n-1, m)
        return result   m;
    }
}

int main()
{
    cout << f(3, 10);
}

We can imagine each function execution (starting with main) as a box (a frame), in which local variables live their lives. Each recursive call creates a new box, and when return is executed that box vanishes again.

So we can imagine the above code to execute like this:

 -[main]---------------------------- 
|  f(3, 10) ...                     | 
|   -[f]-------------------------   |
|  |  n = 3, m = 10              |  |
|  |  f(3-1, 10) ...             |  |
|  |   -[f]-------------------   |  |
|  |  |  n = 2, m = 10        |  |  |
|  |  |  f(2-1, 10) ...       |  |  |
|  |  |   -[f]-------------   |  |  |
|  |  |  |  n = 1, m = 10  |  |  |  |
|  |  |  |  return 0       |  |  |  |
|  |  |   -----------------   |  |  |
|  |  |  result = 0           |  |  |
|  |  |  return 0   10        |  |  |
|  |   -----------------------   |  |
|  |  result = 10                |  |
|  |  return 10   10             |  |
|   -----------------------------   |
|  cout << 20                       |
 -----------------------------------

I hope this clarifies it.

CodePudding user response：

The algorithm solves the recurrence

F(n) = F(n-1)   m

with

F(1) = 0.

(I removed m as an argument, as its value is constant).

We have

F(n) = F(n-1)   m = F(n-2)   2m = F(n-3)   3m = ... = F(1)   (n-1)m.

As written elsewhere, the recursion depth is n, which is dangerous.