How far does recursion execute into your function in C++?

Question

I've written recursive functions with the guidance of a friend who is teaching me C++ (as a first language). However, I don't really understand what is going on. He helped me (and the SO community, as well) write a merge sort function.

std::vector<int> mergeSort(std::vector<int> original)

//code here to create two vectors, farray and sarray, out of the 
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int

farray = mergeSort(farray);
sarray = mergeSort(sarray);

//code here merges the two into a single, final sorted std::vector   

In this function, I assign:

farray = mergeSort(farray);
sarray = mergeSort(sarray);

What exactly is happening here? It calls mergeSort with farray and sarray as parameters and changes the value. How far does mergeSort execute into itself recursively? Just upto the recursive function call?

Answer 1

Each time you call a function recursively, it effectively makes a new copy of the information it needs, and goes on.

You could have a program that recurs "infinitely", ie, until it runs out of resources, usually stack space — the space in which those copies are going. That would look like

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

Obviously, this isn't very useful, so you want to write a program that has some limit on how often it recurs. Here's a really simple program that manages that:

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

If you compile and run that, say with:

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

You'll get the results:

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $ 

See how it gets called for 10, then 9, and so on, and then after it reaches the bottom, it shows it coming back for 1, then 2, and so on back up to 10?

The basic rule is that every recursive function should have something that makes a base case, one which does call itself again. In this one, the base case is count == 0 and in fact we could have written this as a recursive definition

recursome:
if c = 0 : print bottom
if c > 0 : print count, and recursome(c-1)

You'll see many recursive definitions of that sort as you move on in math.

Here's a somewhat niftier C version with better output:

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

Output:

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10

Answer 2

Check it out in the dictionary:

recursion: noun. see recursion

Now, being serious, in the joke above, the definition of recursion is given in terms of recursion itself. That is recursion.

A recursive algorithm is an algorithm whose implementation is based on the algorithm itself. The process of developing such an algorithm starts with the most basic case, whose solution is either known in advance or can be trivially calculated. Then you define the algorithm in terms of itself.

As a simple example, calculating the n-th power of a given integer i could be a function power( int number, int power ). How could you implement it? in many ways. The simplest being a call to a library, followed by a loop, or you could define the function in terms of itself:

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

We have defined the function in terms of itself. You start with the most basic case (n^0 = 1). If we are not in the simplest case, you can express your algorithm in terms of itself.

The program would start in main by calling power( 2, 10 ) that would recurse and call power( 2, 9 ) reducing the problem to a smaller problem and would then compose the final answer in terms of the simpler problem.

The actuall call trace would be:

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

While developing recursive algorithms it usually helped me believing that I already had the algorithm up and running and just work on the reduction/composition of the new result.