How deos recursion work?

[ITFreak]

Could anybody please explain me the working of this program.
It gives output: 55.

#include <iostream.h>
int whatIsThis( int [ ], int );

int main()
{
    const int arraySize = 10 ;
    int a[ arraySize ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 };
    int result = whatIsThis( a, arraySize );
    cout << "Result is " << result << endl;
    return 0 ;
}

int whatIsThis( int b[], int size )
{
    if ( size == 1 )
        return b[ 0 ];
    else
        return b[ size - 1 ] + whatIsThis( b, size - 1 );
}

[Disch]

Recursion is just a function calling itself. Here, whatIsThis is calling whatIsThis repeatedly to calculate its output.

What's basically happening is that 'size' is counting down each time it's called. And each time, it sums the last element in the provided array.

So...

whatIsThis(a,10) ==  whatIsThis(a,9) + a[9]
whatIsThis(a, 9) ==  whatIsThis(a,8) + a[8]
whatIsThis(a, 8) ==  whatIsThis(a,7) + a[7]
...
whatIsThis(a, 2) ==  whatIsThis(a,1) + a[1]
whatIsThis(a, 1) ==  a[0]

The end result is that it returns the sum of all elements in the provided array, which in this case is 55.

[ResidentBiscuit]

Recursion is fun stuff. It's used a lot through math. Fibonacci sequence, factorials, etc.

[eypros]

Recursion is a special technique used in programming. Basically it's what @Disch said: a function that calls itself.

In every recursion the calling function calls itself. Of course to be a working program there should be a terminating condition. Here it's the second argument (int size).

As you can see when this happens to be 0 then the function instantly returns (line 16). The structure that is created is eventually calculate when the last non recursive function returns. Then every function that has been called starts to return and finally the first called function returns and program goes to line 9.

If you want you can run a variation of the problem to see the order of calling functions:

int whatIsThis( int b[], int size )
{
    if ( size == 1 )
        return b[ 0 ];
    else
    {
        int i = whatIsThis( b, size - 1 );
        cout << "size is" << size << " whatIsThis( b, size - 1 )=" << i;
        return b[ size - 1 ] + i;
    }
}

As you can see recursion requires a great amount of memory since all these functions need to be called (every function requires extra space since it's called inside another same function).