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
> 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

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

--
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
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

 Page 1 of 1 [ 5 post ]

Relevant Pages