c++ Recursion array explanation

Question

Hello i am learning recursion and currently i have couple of trick problems to dissect - here is one of recursive functions

int rec(int niz[], int start, int end){

if (start == end)
{

    return niz[start]; // vraca zadnji
}

int temp = rec(niz, start+1, end);


// control output
cout << "\n-----\n";
cout << "start "  << start << endl;
cout << "niz[start] "  << niz[start] << endl;
cout << "end "  << end << endl;
cout << "temp "  << temp << endl;
cout << "\n-----------------------------------------\n";
//contrl output end

return ((niz[start] < temp) ? niz[start] : temp);
}

i included a cout block to control what is gong on in calls. here is main part

    int niz[] = {1,2,3,4,5,6,7}; 
    cout << rec(niz, 0, 3);

and here is my output:

-----
start 2
niz[start] 3
end 3
temp 4
------------------

----- 
start 1
niz[start] 2
end 3
temp 3
------------------

-----
start 0
niz[start] 1
end 3
temp 2
------------------

1

can anyone explain me how is temp value being calculated and returned and how i am getting 1 as the return of this function?

Thank You in advance!

Answer 1

Recursive function is the function that calls itself.

int temp = rec(niz, start+1, end);

Here you call the "rec" function inside the one, but with the changed parameter (start + 1). You call these function inside each other until the "start" equals "end" (then it returns)

if (start == end)
{

    return niz[start]; // vraca zadnji
}

After the deepest one returns the second deepest one continues its flow, printing some information.

cout << "\n-----\n";
cout << "start "  << start << endl;
cout << "niz[start] "  << niz[start] << endl;
cout << "end "  << end << endl;
cout << "temp "  << temp << endl;
cout << "\n-----------------------------------------\n";

Then it it returns the lowest value between niz[start] and temp (local values).

return ((niz[start] < temp) ? niz[start] : temp);

Then the third deepest one continues its flow and so on. Until it gets to the first function.

In your main part you set the end to 3, so it performs the operation on the first 3 elements (it gets to the fourth element, but doesn't do anything beside returning its value). You get 1 by comparing the niz[0], that you passed as start, and temp that is returned by recursive function (which happens to be the same). It equals, so the return value is niz[0] that is 1;

When using recursive functions, you should have some kind of "exit point" that prevents the recursion to become infinite, i.e.

if (start == end)
{   
    return niz[start];
}

In general, recursive functions look like this:

f()
{
    //return condition
    //some work
    f();
    //some work
    //return
}

And you can look at them as this

f()
{
    //some code
    f()
    {
        //some code
        f()
        {
            //some code
            f()
            {
                ...
                //eventually the return condition is met
            }
            //some code
            //return
        }
        //some code
        //return
    }
    //some code
    //return
}

Keep in mint that unhandled recursion may lead to possible memory leaks, because each function call comes with additional data.

f()
{
    f();
}

This will lead to stack overflow due to system data that has been created;

You may want to watch "Inception" to understand it better :)

Answer 2

 rec(niz, 0, 3)                          (D)
  |
  ---->rec(niz, 1, 3)                    (C)
        |
        ----> rec(niz, 2, 3)             (B)
               |
               ----> rec(niz, 3, 3)      (A)

You call (D) which calls (C) to calculate temp and so on up to (A). In (A) start==end and it returns niz[3]=4.

In (B):

temp = 4 (result of (A))

start = 2

As 4 is bigger than niz[start]=3 (B) returns 3

In (C):

temp = 3 (result of (B))

start = 1

As 3 is bigger than niz[start]=2 (B) returns 2

In (D):

temp = 2 (result of (C))

start = 0

As 2 is bigger than niz[start]=1 (B) returns 1

Answer 3

Your recursive line is before your print statement block. By nature of recursion, it makes the function call on that recursive line and stops the caller function's execution until the callee is done. Therefore you call for the next element to be processed before you print the current element.

In your example the following is happening:

Layer 1:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 2:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 3:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 4:
    Is start equal to end? Yes!
    Return the current element, 4.
    End layer 4.
Layer 3:
    Now know next element, start printing for the 3rd element.
    Return 3.
    End layer 3.
Layer 2:
    Now know the next element, start printing for the 2nd element.
    Return 2.
    End layer 2.
Layer 1:
    Now know the next element, start printing for the 1st element.
    Return 1.
    End layer 1.
End program.

As you can see, the array elements are printed backwards because the print statements are after the recursive call. I'd you want them to be printed in order, print them before the recursive call, or create a buffer and append each print section to the front of the buffer.