How much recursion is performed in your function in C ++?

Question

I wrote recursive functions with the guidance of a friend who teaches me C ++ (as the first language). However, I do not quite understand what is happening. 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 going on here? It calls mergeSort with farray and sarray as parameters and changes the value. How far does mergeSort perform in itself recursively? Just before calling the recursive function?

Answer 1

Each time you call a function recursively, it effectively creates a new copy of the information it needs and continues.

, "", .. , , - , .

void recur(){
    recur();
}

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

, , , , . , :

#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. */
}

,

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

:

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 $ 

, 10, 9 .., , , , 1, 2 .. 10?

, -, , . count == 0

recursome:
     c = 0:      c > 0: recursome (c-1)

, .

C :

#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. */
}

:

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

:

: . .

, , . .

- , . , , . .

n- power( int number, int power ). ? . , , :

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 );
}

. (n ^ 0 = 1). , .

, power( 2, 10 ), power( 2, 9 ), .

:

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

, , / .

Answer 3

. P (n) n, P (n) " 1 n n (n + 1)/2", :

• : P (n) . P (1) , 1 = 1 (1 + 1)/2.
• : P (n) , P (n + 1) . 1 +... + n + (n + 1) = n (n + 1)/2 + (n + 1) = n (n + 1)/2 + 2 (n + 1)/2 = (n + 1) ((n + 1) +1)/2, P (n + 1).

, , mergeSort, :

• : , ;
• : , .

, , . , log2 (n).

, :

• .
• farray sarray .
• - std::vectors, . mergeSort :: , std:: sort().

mergeSort .

Answer 4

, - , , . , .

, , 1 , mergeSort()? .

, farray sarray , mergeSort() , .

, 2 , 1? mergeSort() 2, 1.

mergeSort() mergeSort() sarray , .

Answer 5

Take a look at the wikipedia page for merge sort for more information on what you're trying to do.

As an alert, remember that you are making a copy of each vector that you specify as a parameter. Use the vector <> const & instead.