understanding recursion

[4ET0pfjN]

Here's a related function I found online, why does it work b/c doesn't it constantly return smallResult with element at index 0?

int sum( int arr[], int n )
{
  if ( n == 0 )
    return 0;
  else
    {
       int smallResult = sum( arr + 1, n - 1 ); // "A"

       return smallResult + arr[ 0 ];//Isn't arr[0] always element 2
    }
}

int main()
{
   int list[3] = {2,4,6};
   cout << sum(list, 3);
   return 0;
}

[kbw]

Isn't arr[0] always element 2

No.

For the first call, arr is { 2, 4, 6 }, so arr[0] is 2.

For the second call, you pass in arr + 1, which is { 4, 6 }, so arr[0] is 4. And so on.

This way of list processing is more conventional, the conventions being set by LISP. The idea is, you treat a list as [ first element, the rest ].

Your example just worked from back to front, but the principle's the same.

[4ET0pfjN]

I tried to trace this and on the stack I reach:

main -> sum(&arr[0], n = 3) -> sum(&arr[1], n = 2) -> sum(&arr[2], n = 1) -> sum(&arr[3], n = 0)

So we hit base case and return 0, then we go to caller line A and assign to int smallResult 0, then we go to the next line (return) and smallResult is 0 added to the current first element of arr, but which is &arr[3] which doesn't exist unless once we reach base case, we immediately pop off the sum(&arr[3], n = 0) so top of stack is actually sum(&arr[2], n = 1). Is that right?

So we are actually adding the elements of array backwards.

Also, I want to make sure, whenever we reach return keyword, we immediately pop off from stack top.

[kbw]

Do you have a debugger you can run your programs in?

If you do, step through the program one line at a time. You'll be able to see the values of auto variables, you can watch memory on the heap, register values, the call stack; everything you need.

[4ET0pfjN]

So we are actually adding the elements of array backwards.

Also, I want to make sure, whenever we reach return keyword, we immediately pop off from stack top.

I will look into a debugger but is the above I quoted of my previous post correct. I have never used it ever I admit, the only debugging I do is using cout to such as in for loops etc.

[4ET0pfjN]

I think I'm messing up when we reach the base case, like for this simple counting up function. I thought zero would be pushed onto the stack, but it's not.

void recursive_countUp(int p) //NOT tail recursive since we do something after popping each recursive fcn called from stack (return to caller I mean)
{ 
   if (p == 0) 
	return;//Q: why isn't 0 outputted? A: I think it's b/c it's void so we return nothing...Or maybe base case it NOT stored on stack...not sure
	
   recursive_countUp(p-1); //line A
   cout << p << " "; //line B
   return; //implicit so don't need this return statement in void so it will return to caller so print 1, then we return to line A and pop 2 off stack, print 2 
	//	then return to caller again (this fcn) so go back to line A and pop 3 //line C (implicit return statement)
}

[kbw]

So we are actually adding the elements of array backwards.

Yes.

whenever we reach return keyword, we immediately pop off from stack top.

Yes.

Have you seen mathematical recursive definitions? You define exit conditions and recursive conditions. The premature exit matches the exit conditions in the definition.
For example: http://en.wikipedia.org/wiki/Factorial#Definition

I thought zero would be pushed onto the stack, but it's not.

So would I. Are you debugging optimised code or is it built for debug?

[4ET0pfjN]

I'm going to keep bugging everyone until I get it (recursion I mean). I wrote this reversed string function and I had to admit I was thinking about the stack to reverse rather than any logic of thinking of a sub-problem, it compiles, but it only outputs: cb.

I'm going to guess this would not be a great example of deploying recursion if the solution doesn't come naturally to be thought of in terms of a sub-version of initial problem such as a count down timer...

void reverse_string_v2(string *list, int size, int curIndex)
{
   if ( curIndex == size - 1 )
	return;
   else
	reverse_string_v2(list, size, curIndex = curIndex + 1);
   cout << list[curIndex];
}

int main()
{
   string *list_b = new string[3];
   *list_b = "a"; 
   *(list_b + 1) = "b"; 
   *(list_b + 2) = "c";
   reverse_string_v2(list_b, 3, 0);
}

[kbw]

Why are you changing the value of curIndex?

reverse_string_v2(list, size, curIndex = curIndex + 1);

Also, please don't do this:

   *list_b = "a"; 
   *(list_b + 1) = "b"; 
   *(list_b + 2) = "c";

Do this instead.

   list_b[0] = "a"; 
   list_b[1] = "b"; 
   list_b[2] = "c";

[4ET0pfjN]

I've tried with:
reverse_string_v2(list, size, curIndex + 1); and I get output:ba

then I tried:
reverse_string_v2(list, size, ++curIndex); and I get output:
cb

What am I doing wrong that's causing it to miss an index?

[kbw]

If you want to reverse the content of an array, you need to start with the correct algorithm:

swap: array, len
  if len < 2 return
  swap first and last. swap(first + 1, len - 2)

This translates to:

#include <iostream>

void reverse(char *a, size_t len)
{
        if (len < 2)
                return;

        char tmp = a[0];
        a[0] = a[len - 1];
        a[len - 1] = tmp;

        reverse(a + 1, len - 2);
}

int main()
{
        char str[] = "abcde";
        reverse(str, 5);
        std::cout << str << std::endl;
        return 0;
}