understanding recursion

[4ET0pfjN]

Hi, so recursion works as all functions where each time we invoke a function, on the stack a dedicated stack frame is available where the next function in line is added to top of this stack (in its stack frame w/ all its arguments, local variables to that function), but with recursion its multiple stackframes for each smaller version of the same function so how does recursion do multiple things at once which explains why merge sort and quick sort are faster than loops w/ bubble sort, insertion, selection sort for eg? Because only the top stack frame is executed unless we call recursion multiple times, so hence multiple work, is that right? Anyone...

[kbw]

so how does recursion do multiple things at once

Recursive functions don't do everything at once.

The environment doesn't know that it's the same function being called recursively and there are no special rules for a function that calls itself vs one that calls another function.

Recursive algorithms are not faster than the equivalent loop version of the algorithm.

[4ET0pfjN]

I've took algorithms course before dropped out b/c of personal reasons and merge sort and quick sort were faster, so it's not b/c of recursion, but if a recursive function in general is called multiple times, in effect it is doing mutliple work at once since each has its own set of stack frames...no?

[kbw]

No. Multiple threads can do work at the same time. A recursive function is just doing one thing at a time like any other function call.

[hanst99]

Why "learn" recursion? It's a very natural thing:

0) To sort a deck of cards: designate an empty place where the sorted deck goes.
1) If your deck is empty, you are done sorting it.
2) If not, take the top card from the deck and insert it into the right position in your already sorted deck.
2.1) Continue at 1.

The primary reason recursion is used is because recursive solutions are usually a lot easier to conceive and understand than iterative solutions, as they are only dealing with small parts of the problem at each step.

Oh and it has nothing to do with stack frames, that's just an implementation detail you have to be aware of when your recursion get very deep.

[ne555]

I don't see the recursion in your example.
I think I've got it

sort( List, Sorted ) :- sort( List, [], Sorted ).
sort( [], Sorted, Sorted).
sort( [X|List], Aux, Sorted ) :- 
  inorder_insertion(X, Aux, Augmented),
  sort( List, Augmented, Sorted).

[hanst99]

I certainly wasn't thinking of Prolog when I wrote that, but yeah that's the idea.

[4ET0pfjN]

let's say I want to search for a node in a singly linked list as such:

struct node
{
 string data;
 node *next;
};

node *search(node *list, string data)
{
  if ( list == NULL ) return NULL;
  
  else if ( list->data == data ) return list;

  else return search(list->next, data);
}

Let's use example:

int main()
{
 node *list = NULL;
 list =   insert_at_front(list, "C");
 list =   insert_at_front(list, "B");
 list =   insert_at_front(list, "A");
 
 search(list, "C");

 return 0;
}

Our list is now: "A"->"B"->"C"->NULL

So main calls search and stack so far:

(bottom of stack so far):main

Then "A" not same as data, so search function calls itself so now our stack:

main->search level 1

Then "B" not same as data, so search function calls itself so now our stack:

main->search level 1->search level 2

Then "C" matches data so we return list (so where is list on the stack?)

When do I pop off to return to caller search, I know I'm making it harder than it looks, but recursion gets me...

[kbw]

So your call stack looks like:
main()
search(->"A"->"B"->"C", "C")
search(->"B"->"C", "C")
search(->"C", "C")

And you're at line:

 else if ( list->data == data ) return list;

It returns the pointer to the node with "C"

Call search(->"B"->"C", "C") will be at line:

  else return search(list->next, data);

which returns the the return value from search(->"C", "C"), which is the pointer to the node with "C"

Call search(->"A"->"B"->"C", "C") will be at line:

  else return search(list->next, data);

which returns the the return value from search(->"B"->"C", "C"), which is the pointer to the node with "C"

So the value that main receives (but ignores in your code) is a pointer to the node with "C".

[4ET0pfjN]

The reason I'm having trouble is b/c I'm used to thinking about recursion where once we reach base case, we return the value which gets appended to the other return statements so I mean we have to do something w/ the return statement when we give back to caller. I always think back to classic (I guess not helpful) factorial e.g. that's why I'm asking once we find the node and return list (which is pointer to the node we found), what do we do with it...but I guess it's just like any non-recursive function where we can choose to assign the function to a variable or just call the function as is

int factorial(int n)
{
  if ( n == 1 )
    return 1;
  else
   return n*factorial(n-1);
}

*In pertaining to my original post, so once we find "C' node, list returns pointer to it, which then goes back to caller, search which then the stack frame is now currently: search(->"B"->"C", "C") which you say is also returning a pointer to "C" node? So we return pointer to "C" node three times, right?

Also, what happens if the node wasn't found (I'll use same list but search for D, then we execute the base case and return NULL, so NULL is returned to the caller which is search function which then the other two levels of search are returned but what do they return...i'm starting to not make sense...And what do you mean the value main receives but ignores in my code?

[kbw]

what happens if the node wasn't found

Null is returned.

And what do you mean the value main receives but ignores in my code?

You don't store the value returned by search().

[4ET0pfjN]

so when I try to find "C", we find it and search function returns ptr to "C" three times in this case (my original post I mean), right? b/c depending on what we wanted to do, each return of pointer "C" I could have decided how the search function decided to do with that value, but in this case it doesn't do anything unlike the factorial function where each return (pop of factorial off stack) chooses to multiply the returned value, is that correct?

Also, this would be e.g. of tail recursion unlike factorial function?

Also, w/ factorial e.g. on stack don't we store:

main->factorial(3)->factorial(2)->factorial(1) so how can the non-base case multiple n*factorial(n-1) or are we storing on stack:

main->3->2->1

which means we are only storing the arguments passed in function, is that right?

Again, I appreciate your help, kbw.

[kbw]

I could have decided how the search function decided to do with that value, ..., is that correct?

Yes.

Also, this would be e.g. of tail recursion unlike factorial function?

I don't quite understand this.

main->factorial(3)->factorial(2)->factorial(1) so how can the non-base case multiple n*factorial(n-1) or are we storing on stack:
main->3->2->1
which means we are only storing the arguments passed in function, is that right?

I don't quite undestand the question, but the answer is, I don't think so. Look at it this way. When a C function that has a return value is called, this is what happens.
1. The caller pushes the arguments onto the call stack in left to right order.
2. The function is called. Before it returns, it places the return value in a register.
3. The caller pops the arguments from the stack.
4. The called picks up the return value from the register.

So you can think of the return value from a function call being placed in a temporary variable that you never quite see. Your factorial code is really something like:

int factorial(int n)
{
  if (n < 2)
    return 1;

  int tmp = factorial(n - 1);
  int val = n * tmp;
  return val;
}

The rules are quite simple and there's no special case for the seemingly different ways functions are used.

[4ET0pfjN]

would it be the same w/ void functions with implicit return?

[kbw]

void functions with implicit return?

Can you give an example of what you mean please.

[4ET0pfjN]

void printNum(int n)
{
  cout << n;
  
  if ( n < 9 )
     printNum(n + 1);
  
  cout << n;
}

int main()
{
  printNum(1);
}

It's supposed to output:
123456789987654321

Actually, this outputs to console so I'm not sure, but for the factorial e.g. (forget about void recursion, I'm not sure), once the base case of 1 is reached, it is returned to the same caller factorial but is one stored on the stack?

[hanst99]

Whether or not Compilers take advantage of optimizing tail calls is entirely up to them. Although I am still a little fuzzy on the details I am 100% sure that the example you gave is not tail recursive (printNum that is, I think your factorial might be).

[kbw]

I that example where the function return type is void, it means the function doesn't return anything.
1. The called function doesn't place a value in the register.
2. The caller function doesn't expect to find a value there.

That's why the language needs function prototypes, so it can enforce type rules.

[4ET0pfjN]

Here's another e.g. to hopefully clarify recursion:

let's say function that sums the first n elems in an array:

int sum( int *arr, int n )
{
  int sum;
  if ( n == 0 )
    return 0;
  else 
    {
       sum= sum( arr, n - 1 );  // line A
       return sum + arr[ n - 1 ];   // line B
    }
}

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

Winding process: (bottom of stack is leftmost function)
==================================
0)Main function initially calls sum

(stack bottom)main->sum(arr, 3)(stack top)

1)3 != 0, so run else so n = 2

main -> sum(arr, 3) -> sum(arr, 2)

2)we call function sum again and now 2 passed and 2 != 0 so run else with n = 1

main -> sum(arr, 3) -> sum(arr, 2) -> sum(arr, 1)

3)we call funciton sum again, and 1 != 0 so run else with n = 0

main -> sum(arr, 3) -> sum(arr, 2) -> sum(arr, 1) -> sum(arr, 0)

Unwinding process:
==============

main -> sum(arr, 3) -> sum(arr, 2) -> sum(arr, 1)

1) so n == 0 now so we return 0 to caller sum (line A)(pop sum(arr, 0) off stack and int sum = 0, then we run line B so total + arr[1-1] since top of stack is sum(arr, 1) and pop this off stack so index 0 so we return 0 + element at index 0:2 so we return 2 to caller which is function sum.

main -> sum(arr, 3) -> sum(arr, 2)

2) so we go back to line A, and now int sum = 2. Now we run line B
which is 2 + arr[2 - 1] so index 1 since stack top is sum(arr, 2 ) where n = 2
so what we return is: 2 + 4 = 6 so we return 6 to caller: sum and pop off sum(arr, 2)

main -> sum(arr, 3)

3) we go back to line A, and int sum = 6. Then we go to line B, so
6(current value of sum) and add to arr[3 - 1] so index 2 (since n = 3, since current top o stack is sum(arr, n = 3) so the sum is: 6 + 6 = 12 and we return to caller: main and pop off sum(arr, 3).

4) 12 returned to function: main and main popped off by whoever called it, program terminates!

[kbw]

Seems about right.

But you do have a syntax error:

       int sum= sum( arr, n - 1 );  // line A