Recursive function? [beginner]

Question

I don't understand recursive functions.

I wrote this code to help me but i don't understand why it works the way it does.

It prints backwards the steps from 0 to the number n/2 i input but don't know what makes it print every step it skipped from low to high because it went recursive. I am close but not yet there...

#include <iostream>
#include <conio.h>
using namespace std;

int recursiv(int );

int times;

int main(){    
    int x;    
    cout<<"Imput number\n";
    cin>>x;    
    recursiv(x);

    getch();
  return 0;
}
int recursiv(int x){

    times++;
    if(x)
    recursiv(x/2);
    cout<<"We are now at "<<x/2<<endl;
    if (!x)
    cout<< "We reached "<<x<<" but it took "<<times-1<< " steps\n";
    return 0;
}

Answer 1

When you are dealing with recursion you have to understand two main part of the function code: the one that is executed on the way forward, and the one that is executed on the way back:

void X() {
    // way forward
    X();
    // way back
}

The way forward part is executed while calling the function over and over until the end of the recursion; the way back is executed while coming back from the last call to the first.

void print(int x) {
    if (!x) return; // end of recursion
    std::cout << x << " ";
    print(x-1);
}

The above example contains std::cout << x on the way forward which means that the call print(5) will print: 5 4 3 2 1.

void print(int x) {
    if (!x) return; // end of recursion
    print(x-1);
    std::cout << x << " ";
}

The above example moved the actual printing to the way back part of the function which means that the same call print(5) will print: 1 2 3 4 5.

Let's take your function (cleaned up a bit):

int recursiv(int x){
    times++;
    if(!x) return 0; // split
    recursiv(x/2);
    cout << "We are now at "<< x / 2 << endl;
    return 0;
}

We can distinguish our two parts quite easily. The way forward is:

times++;
if(x) return;

In which we just increment our int parameter times (we just ignore the conditional for the end of recursion here).

The way back is:

cout<<"We are now at "<<x/2<<endl;
return 0;

Which will be executed from the last call to the first one (just like the second version of the example). Therefore taking from the lowest number (the one nearer to 0 because of the end recursion condition) which is the last called before the end of recursion to the first, just like our example.

Answer 2

If i understand your question correctly:

It should print from high to low, but it actually prints from low to high. why is that?

The line cout<<"We are now at "<<x/2<<endl; is after the call for recursion. so the function calls itself with a smaller amount again and again until it hits the break criteria. the the function with the smallest amount calls the std::cout, return the second smallest amount does the std::cout and so on until the last one does it.

If you want the result in the other order, move the mentioned line two lines higher, so each iteration echos before calling the child.

example:

int recursiv(int x, int times = 0) {
  std::cout << "We are now at " << x/2 << std::endl;

  if(x)
    return recursiv(x/2, times + 1);
  else
    std::cout << "We reached " << x << " but it took " << times << " steps" << std::endl;

  return 0;
}

Unrelated: Global variables are considered a bad practice. There are use cases for them, this is not one of them. I fixed that within the function.