Comments as //!!
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//!! these should be declared as const pointers
//!! also, adding names does no harm either as it helps to document the function
//!! void reverse ( const char *start, const char *end );
void reverse(char *, char *); /* here is where the recursion happens */
//!! there is no need to prototype main - you shouldn't even try.
int main(void);
int main() /* examine pointer math, recursion */
{
//!! the indentation should be consistent
//!! the pointers should be const char *
char *srcstr;
char *startp;
char *endp;
int slen;
//!! this is non-portable.
system("clear");
printf("\nProgram begin.\n\n");
//!! beware of meaningless comments - why is 78 significant here?
srcstr = "abcdefghijklmnopqrstuvwxyz0123456789 The hot brown fox swam in the cool lake."; /* 78 characters */
startp = srcstr;
//!! perhaps it would have been better to declare slen as a size_t instead.
slen = (int) strlen(srcstr);
//!! NULL (4 letters upper case is used when referring to the pointer that points nowhere.
//!! nul (3 letters lower case) refers to the character with value '\0'.
endp = startp + (slen - 1); /* without the "slen - 1", endp would point to the NULL character terminating the string */
printf("Character string (length %d): %s\n\n", slen, srcstr);
//!! to print with %p, you should really cast the pointer to void*
//!! eg. printf("%p",(void*)startp);
//!! also, talking about 'hex addresses' supposes that %p prints in hex.
//!! The standard simply states that %p renders a void* pointer as
//!! "a sequence of printing characters, in an implementation-defined manner."
printf("\"startp\" contains memory-space address %p, which points to '%c'\n", startp, *startp); /* doing subtraction on the hex */
printf("\"endp\" contains memory-space address %p, which points to '%c'\n\n", endp, *endp); /* addresses gives us 77, which */
/* is explained by how we count */
printf("Character found at \"startp + 5\": %c\n", *(startp + 5)); /* from start-point of the string */
printf("Character found at \"startp + 26\": %c\n\n", *(startp + 26));
printf("Reversed string:\n\n");
reverse(startp, endp);
//!! to me, this seems like a hacky bug caused by poor code.
printf("%c\n\n", *startp); /* our silly reverse() function fails to print endp when endp = startp */
/* so we have to accommodate this quirk and print startp for completeness */
printf("Done.\n\n");
return(0);
}
/* description: we first enter this function with startp pointing to the beginning of the string */
/* and endp pointing to the end of the string. As both pointers are clearly NOT */
/* pointing at the same memory-space location, we print the CONTENT of endp (which */
/* is the last character of the string). Then we decrement the pointer. */
/* Nothing says we can't - at this point IN reverse() - call the reverse() function */
/* which starts the recursion. This cycling continues, decrementing endp, until */
/* endp = startp, at which point THE RECURSION STOPS and the "layers of function */
/* calls" effectively evaporate. */
/* Imagine... You walk outside your house, and see 13 pieces of trash in your yard. */
/* Your job is to throw away each piece of trash. So, you get the first */
/* piece of trash, and throw it away. Now, INSTEAD of walking over to */
/* the next piece of trash, you CLONE yourself, and wait for your CLONE */
/* to handle the next piece of trash. So your CLONE gets the next trash */
/* and throws it away, then waits. He creates another CLONE, who gets */
/* the next bit of trash to throw away. This continues until there are */
/* 12 CLONES of you (plus you) standing in the trash-free yard, at which */
/* point all your CLONES disappear. It could be said you alone did all */
/* the work, but in an unusual manner. In the real world, you would do */
/* the cleanup by sequentially getting and disposing each trash item. */
//!! I don't think the idea of CLONES is really that helpful. There is no CLONEing going
//!! on when one function calls another function, any more than when one function calls itself.
//!! There is simply a memory of where you were, so you can get back to where you left off
//!! when you're done.
//!! The trash yard example can be simply stated as:
//!! if there is a piece of trash in front of you, pick that up first, otherwise pick up
//!! the piece of trash behind you.
void reverse(char *startp, char *endp)
{
if (startp != endp)
{
printf("%c", *endp);
endp--;
reverse(startp, endp);
}
}
Here's my take on reverse.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void reverse2(const char *s, const char *e) {
if ( e > s ) {
printf("%c",*--e);
reverse2(s,e);
}
}
int main()
{
const char *a = "hello";
printf("reverse of >>%s<< is >>",a);
reverse2(a,a+strlen(a));
printf("<<\n");
const char *b = "";
printf("reverse of >>%s<< is >>",b);
reverse2(b,b+strlen(b));
printf("<<\n");
const char *c = "this is magic";
printf("reverse of word in >>%s<< is >>",c);
reverse2(c+5,c+7);
printf("<<\n");
return(0);
}
There's no messy -1 when working out the end of the string, and no even messier having to print the first characters of the string separately.
Recursion can be good when you have self-similar problems.
Code:
int factorial ( int n ) {
if ( n == 1 ) return 1;
else return n * factorial(n-1);
}
int strlen ( const char *p ) {
if ( *p == '\0' ) return 0;
else return 1 + strlen(p+1);
}
Also, any recursive function can also be expressed as a non-recursive function containing only a loop (and possibly a queue).
Code:
int factorial ( int n ) {
int result = 1;
for ( i = 2 ; i <= n ; i++ ) {
result *= i;
}
return result;
}
int strlen ( const char *p ) {
int len = 0;
while ( *p++ != '\0' ) len++;
return len;
}
Originally Posted by GReaper
