getting confused with recursion 
Author Message
 getting confused with recursion

hey,
i'm just starting to read the K&R, but i've got a short question about
recursion.
A good example in this book is the Quicksort algorithm by C. A. R. Hoare. In
the function qsort this function is called two times. now is the call equal
to a goto in basic, or does it behave like a gosub command? i mean, if the
function is done, does the code return to the line after the recursive
function call, or does it return to the end of the function?


Fri, 04 Feb 2005 18:12:16 GMT  
 getting confused with recursion

Quote:
> A good example in this book is the Quicksort algorithm by C. A. R. Hoare.
In
> the function qsort this function is called two times. now is the call
equal
> to a goto in basic, or does it behave like a gosub command? i mean, if the
> function is done, does the code return to the line after the recursive
> function call, or does it return to the end of the function?

IIRC: It works by invoking the function again (optionally with new
parameters) and returning control to the calling function (itself in this
case) at the next line of code, just as if any other function was calling
it.


Fri, 04 Feb 2005 18:29:39 GMT  
 getting confused with recursion

Quote:

> hey,
> i'm just starting to read the K&R, but i've got a short
> question about recursion.
> A good example in this book is the Quicksort algorithm
> by C. A. R. Hoare. In the function qsort this function
> is called two times. now is the call equal to a goto in
> basic, or does it behave like a gosub command? i mean,
> if the function is done, does the code return to the
> line after the recursive function call, or does it
> return to the end of the function?

A recursive function call works just like any other function call, and can
return a value back to the caller. It's more like GOSUB than GOTO. However,
control doesn't return to the next line, but back into the same line. This
is so that the recursive call can return a value to be used in the
expression in which the call was made.

Let me explain by way of an example. There is a function called "factorial"
and it has results like this:
  factorial(0) == 1
  factorial(1) == 1
  factorial(2) == 1 * 2
  factorial(3) == 1 * 2 * 3
  factorial(4) == 1 * 2 * 3 * 4
  factorial(5) == 1 * 2 * 3 * 4 * 5
  ...

The best way to implement this function is NOT through recursion. However
there is a simple recursive implementation which can be useful to help
beginners to understand how recursion works.

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

Here are the steps of decomposition that you can follow if you evaluate
each recursive call by hand.
  factorial(5)
  5 * factorial(4)
  5 * 4 * factorial(3)
  5 * 4 * 3 * factorial(2)
  5 * 4 * 3 * 2 * factorial(1)
  5 * 4 * 3 * 2 * 1 * factorial(0)
  5 * 4 * 3 * 2 * 1 * 1

First make sure you can get your head around a simple example before trying
to understand a quicksort :-)

--
Simon.



Fri, 04 Feb 2005 18:37:27 GMT  
 getting confused with recursion
Submitted by "Der Alekz" to comp.lang.c:

Quote:
> hey,
> i'm just starting to read the K&R, but i've got a short question about
> recursion.
> A good example in this book is the Quicksort algorithm by C. A. R. Hoare. In
> the function qsort this function is called two times. now is the call equal
> to a goto in basic, or does it behave like a gosub command? i mean, if the
> function is done, does the code return to the line after the recursive
> function call, or does it return to the end of the function?

All function calls in C returns to the caller (except for a few
very special once, like exit (and fork in POSIX, which returns
twice)).  So, it's like a gosub, a subroutine call in Basic.

Sort the first part of the array, then return here and sort the
other half of the array (that's mainly it, apart from the code
that determines where the division between the two parts is to
be made).

--
Andreas K?h?ri
--------------------------------------------------------------
Stable, secure, clean, free:  www.netbsd.org



Fri, 04 Feb 2005 18:35:25 GMT  
 getting confused with recursion

Quote:

> hey,
> i'm just starting to read the K&R, but i've got a short question about
> recursion.
> A good example in this book is the Quicksort algorithm by C. A. R. Hoare. In
> the function qsort this function is called two times. now is the call equal
> to a goto in basic, or does it behave like a gosub command? i mean, if the
> function is done, does the code return to the line after the recursive
> function call, or does it return to the end of the function?

Please compile and link the program I have included below, and then
execute the following algorithm, which I call Algorithm A:

1. Run the program.
2. Study the output, using the code as a guide.
3. If you do not yet understand it, execute Algorithm A.
4. Apply what you have just learned to the question you originally
asked.
5. Stop.

#include <stdio.h>

void printspace(int n)
{
  int space = 0;

  while(space++ < n)
  {
    putchar(' ');
  }

Quote:
}

void recurse(int i)
{
  printspace(i * 3);
  printf("This is the first print in recurse(): i is %d\n", i);

  if(i < 10)
  {
    recurse(i + 1);
  }

  printspace(i * 3);
  printf("This is the last print in recurse(): i is %d\n", i);

Quote:
}

int main(void)
{
  recurse(0);

  return 0;

Quote:
}

--

"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton


Fri, 04 Feb 2005 23:37:25 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Class View gets confused

2. GetParent() getting confused

3. GetParent() getting confused

4. Connecting to a remote server (this is getting confusing)

5. Does VC optimize recursion?

6. Help on recursion

7. BUG: MC++ property syntax can cause infinite recursion

8. MC++ tail recursion optimizer bug in virtual function

9. Recursion too deep error

10. Recursion

11. Another recursion question

12. Recursion Question

 

 
Powered by phpBB® Forum Software