Need help on clarifying these recursion functions:

[Bopaki]

I am still getting lost on how RECURSION works.
Can I get some clarification to these two recursive functions:
printIt(int n) and print(int a)

  #include<iostream>

void printIt(int n);

void print(int a);

using namespace std;

int main() {
	
	int n;
	
	cout<<"\nEnter a number: \n";
	cin >> n;
	cout<<" \tWhat is printed on Function [printIt]: \n" ;
	printIt(n);
	cout<<endl <<endl;
	cout<<"\tWhat is printed on Function [print]: \n";
	print(5);
}

void printIt( int n ) 
{
         if(n >= 2)        // recursive case
      	 printIt( n - 1 );  // recursive call
		 cout << n - 1 << endl;
}

void print(int a)
{
    	if (a >= 1)
        {
        cout<< a <<endl;
        print(a - 1);
    }
}

I have never been so confused in my life.....

[Repeater]

Do you understand what calling a function is?

[Bopaki]

Yes I do......

[Repeater]

So what's the problem? It's just calling a function.

What if a = 3? Then we get:

void print(int a)
{
    	if (a >= 1)
        {
        cout<< a <<endl;
        print(2);
    }
}

So what does the function print(2) do?

void print(int a)
{
    	if (a >= 1)
        {
        cout<< a <<endl;
        print(1);
    }
}

So what does the function print(1) do?

void print(int a)
{
    	if (a >= 1)
        {
        cout<< a <<endl;
        print(0);
    }
}

So what does the function print(0) do?

void print(a)
{

}

If you understand what calling a function is, what's the problem? All these functions do is call a function.

[Bopaki]

That was well explained. You make is look very easy, but when one is given a problem from the book to solve it using recursion. One does not see the recursion. There is a problem is the book by Malik to solve an an equation using recursion:

C(n,r) = n!
______
r! (n - r)!

I do not see the recursion here.

[Repeater]

You can write a recursive function to calculate the factorial of a number.

[Bopaki]

Or am I trying to run before I can walk?

[jonnin]

recursion can be tricky but if you think about it carefully, it works JUST LIKE everything else.

consider


long long factorial(unsigned int x)
{
if(x == 0 || x == 1)
return 1;
else
return factorial(x-1) * x;
}

if you put in 3, for example:
is 3 zero or 1?
no, call factorial(2).
is 2 zero or 1?
no, call factorial(1)
is it zero or 1? yes, return 1.
resume control after return statement, we are in factorial(2) now.
2*1 is 2, return it.
resume control after return statement, we are in factorial(3) now.
3*2 is 6, return it,
control returns back to the caller of factorial(3) (main, for example).

so what you are seeing is that it stops what it is doing, calls a function (that happens to be itself, but so what? its the same as if it called any other function, it stops what it is doing and hands control to the called function, that executes until it returns a result, and then it proceeds with the result where it left off. That the function that is called calls another function that calls another function chains this idea, and it is STILL irrelevant that the function called is itself. It works the same way had it called distinct functions or none at all. Each call stops where it is and hands control to the subroutine and waits for that to hand control back.

If you can get to that point, the the fact that it is recursive melts away ... because it works just like everything else.

[JLBorges]

unsigned int C( unsigned int n, unsigned int r )
{
    if( n < r ) return 0 ; // C(n,r) == 0 if n < r (sanity check)

    else if( ( n == r ) || ( r == 0 ) ) return 1 ; // C(n,n) == 1 and C(n,0) == 1
                                                   // the recursion bottoms out

    else return C( n-1, r-1 ) + C( n-1, r ) ; // by Pascal's rule (recursive)
                                              // https://en.wikipedia.org/wiki/Pascal%27s_rule
}

[Bopaki]

Thank you all for your help.
I have a much better understanding of recursion now.