please discuss recursive calls, program provided.

[gdotone]

From Dietel and Dietel

/* Fig. 8.13: fig08_13.c
Using gets and putchar */
#include <stdio.h>

void reverse( const char * const sPtr ); /* prototype */ 6

int main( void )
{
char sentence[ 80 ]; /* create char array */

printf( "Enter a line of text:\n" ); 12

fgets ( sentence, 80, stdin );

printf( "\nThe line printed backward is:\n" );
reverse( sentence );

return 0; /* indicates successful termination */

}/*endmain*/

/* recursively outputs characters in string in reverse order */
void reverse( const char * const sPtr )
{
/* if end of the string */
if ( sPtr[ 0 ] == '\0' ) { /* base case */
return;
} /* end if */
else { /* if not end of the string */
reverse( &sPtr[ 1 ] ); /* recursion step */
putchar( sPtr[ 0 ] ); /* use putchar to display character */
} /* end else */

} /* end function reverse */

I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.

recursively. the function reverse is called until the base case if found.
The pointer sPtr points to '\0'.

Let the sentence be Hello.
I get back olleH.

When is putchar called.

Thanks,

g.

 

[Paul N]

From Dietel and Dietel



/* Fig. 8.13: fig08_13.c

Using gets and putchar */

#include <stdio.h>



void reverse( const char * const sPtr ); /* prototype */ 6



int main( void )

{

char sentence[ 80 ]; /* create char array */



printf( "Enter a line of text:\n" ); 12



fgets ( sentence, 80, stdin );



printf( "\nThe line printed backward is:\n" );

reverse( sentence );



return 0; /* indicates successful termination */



}/*endmain*/



/* recursively outputs characters in string in reverse order */

void reverse( const char * const sPtr )

{

/* if end of the string */

if ( sPtr[ 0 ] == '\0' ) { /* base case */

return;

} /* end if */

else { /* if not end of the string */

reverse( &sPtr[ 1 ] ); /* recursion step */

putchar( sPtr[ 0 ] ); /* use putchar to display character */

} /* end else */



} /* end function reverse */



I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.



recursively. the function reverse is called until the base case if found.

The pointer sPtr points to '\0'.



Let the sentence be Hello.

I get back olleH.



When is putchar called.



Thanks,



g.

It might help to consider a shorter example. Suppose you call reverse("abc"). The function reverse will, if the string is not empty, call itself on the string begining with the second character, then print the first one. So in effect we get:

reverse("bc"); putchar('a');

Buit what does reverse("bc") do? Well, it too calls reverse, then prints its first character. So we now have:

reverse("c"); putchar('b'); putchar('a');

And again:

reverse(""); putchar('c'); putchar('b'); putchar('a');

And now we are calling reverse with an empty string, so nothing happens, leaving us with:

putchar('c'); putchar('b'); putchar('a');

In case it's not clear - in C a string is a succession of characters endingwith a 0. So if you want another string that starts part-way along your first string and goes all the way to the end of it, you can simply use a pointer to the start position in the original string. If instead you want a string that stops before the end of the old one, you will need to allocate some space and build a copy of the relevant part of the first string.

Incidentally, you may need to print a \n at the end to get the last line toprint properly; you have a spare "6" and "12" in your code; and the comment is wrong as you don't use "gets".

Hope that helps.
Paul.

 

[Eric Sosman]

From Dietel and Dietel

Aside: You probably mean "Deitel and Deitel".

/* Fig. 8.13: fig08_13.c
Using gets and putchar */

Aside: The code actually uses fgets(), not gets(). That's
good -- never use gets(), not ever.

#include <stdio.h>

void reverse( const char * const sPtr ); /* prototype */ 6

int main( void )
{
char sentence[ 80 ]; /* create char array */

printf( "Enter a line of text:\n" ); 12
"12"?

fgets ( sentence, 80, stdin );

I've said "never use gets()" and I stand by that advice,
but there *is* one tiny thing gets() does for you that fgets()
does not: It removes the '\n' character from the end of the
line it stores. That is, gets() would have given you the six
characters

'H', 'e', 'l', 'l', 'o', '\0'

but fgets() will store *seven* characters

'H', 'e', 'l', 'l', 'o', '\n', '\0'

This is sometimes a nuisance, as in your program: When you
print the string in reverse the first character printed will
be the '\n', which you probably don't want.

One thing you can do is obliterate the '\n' character,
which requires just a little care because there might not be
one (if fgets() gets to the end of your array before seeing
an end-of-line, it just stores what it's got and goes no
further). Here are two safe ways to obliterate:

char *newline = strchr(sentence, '\n');
if (newline != NULL)
*newline = '\0';

or, making use of a less familiar but no less useful function:

sentence[ strcspn(sentence, "\n") ] = '\0';

The other thing that's often done is to arrange to ignore
the '\n' when you encounter it when processing the input. Many
programs already ignore at least some spaces and tabs and things,
and it's straightforward to include '\n' among the ignored. In
your program the reverse() function recognizes '\0' as the end
of the line; you might have it treat a '\n' the same way (make
sure to test for both: As explained above, the '\n' might not
be present).

printf( "\nThe line printed backward is:\n" );
reverse( sentence );

return 0; /* indicates successful termination */

}/*endmain*/

/* recursively outputs characters in string in reverse order */
void reverse( const char * const sPtr )
{
/* if end of the string */
if ( sPtr[ 0 ] == '\0' ) { /* base case */

This might become

if (sPtr[0] == '\n' || sPtr[0] == '\0')

return;
} /* end if */
else { /* if not end of the string */
reverse( &sPtr[ 1 ] ); /* recursion step */
putchar( sPtr[ 0 ] ); /* use putchar to display character */
} /* end else */

} /* end function reverse */

I don't think I have a good grasp of when putchar( sPtr[ 0 ] ); get called.

recursively. the function reverse is called until the base case if found.
The pointer sPtr points to '\0'.

Let the sentence be Hello.
I get back olleH.

That's strange. I'd expect the screen to look something like

gdotone> fig08_13
Enter a line of text
Hello

The line printed backward is:

olleHgdotone>

.... but your mileage may vary.

When is putchar called.

In the "else" part of the "if" in reverse(), after printing
the reverse of the right-hand part of the string.

Aside: Reversing a string isn't a problem that really calls
out for a recursive solution; an iterative method would be much
more direct. I suppose D&D are using it not as a way to reverse
a string, but as a way to introduce recursion without tying the
student up in a lot of complications -- I have to admit it's a
better problem than the usual Truly Awful exercise of computing
Fibonacci numbers! Still, the typical reason for a recursive
approach is when the "splitting" step produces two or more sub-
problems to be solved recursively. Exploring a maze, for example:

void explore (Junction junction) {
// Here I am at a junction where N corridors branch
for (int i = 0; i < junction.corridorCount; ++i) {
Corridor corridor = junction.corridor;
if (! corridor.explored) {
corridor.explored = true;
explore (corridor.junctionAtOppositeEnd);
}
}
}

The sub-problems are to explore the maze starting from the other
end of each of the N branching corridors; the "super-problem" is
to explore the maze starting from `junction'. Now to explore
the entire (connected portion of) the maze, just clear all the
`explored' flags and call explore(anyJunctionYouCareToStartFrom);
the recursion will follow all possible leads from that point on.

 

[gdotone]

Aside: You probably mean "Deitel and Deitel".

yes, it should be Deitel and Deitel.
my computer corrected the spelling.

/* Fig. 8.13: fig08_13.c
Using gets and putchar */

Aside: The code actually uses fgets(), not gets(). That's

#include <stdio.h>

void reverse( const char * const sPtr ); /* prototype */ 6

int main( void )
{
char sentence[ 80 ]; /* create char array */
printf( "Enter a line of text:\n" ); 12

"12"?

that was a line number. it there do to my editing effort.

fgets ( sentence, 80, stdin );

I've said "never use gets()" and I stand by that advice,
but there *is* one tiny thing gets() does for you that fgets()
does not: It removes the '\n' character from the end of the
line it stores. That is, gets() would have given you the six
characters

'H', 'e', 'l', 'l', 'o', '\0'

The chapter is about: "Standard Input/Output Library Function"

so, i think it's more about showing the use of the functions,
but thanks for the incite of correct usage.

fibonacci is discussed, but i understood the code there.

Is this like pushing these characters onto a stack?
so, as i work down the stack the next line is executed, the putchar()?

my thought was that it actually move down the string of characters one character at
a time, i mean ...

let's say sentence is "abc\0" (following Paul"s thought, he's right it's shorter)
so
when reverse is called
sPtr->abc\0
the else statements are executed
so reverse is called (starting at the address of the second char)
sPtr -> bc\0
the else statements are executed
so reverse is called
sPtr -> c\0
the else statements are executed
so reverse is called
sPtr ->\0
now this the base case so we work back down the stack
( i may not be using terminology stack correctly here)

moving back down (so to speak)
sPtr[0] ->c so execute putchar[sPtr[0]) that prints c
still moving back down
sPtr-> b so execute putchar ... that prints b
still moving back down
sPtr-> a so execute putchar ... that print a

cba

ok that said, that would mean that when a recursive function is called
as it works it way back, after it's base case has been found it should start
execution where it left off which would be after the recursive() call.

Does that make sense?

Ok, i guess that is what you said Paul. thanks

 

[Barry Schwarz]

On Sun, 8 Sep 2013 13:41:04 -0700 (PDT), (e-mail address removed) wrote:

/* recursively outputs characters in string in reverse order */
void reverse( const char * const sPtr )
{
/* if end of the string */
if ( sPtr[ 0 ] == '\0' ) { /* base case */
return;
} /* end if */
else { /* if not end of the string */
reverse( &sPtr[ 1 ] ); /* recursion step */

Since sPtr is defined as a pointer, you can simplify (at least in
terms of typing) the expression &sPtr[1] to the more conventional
sPtr+1.

putchar( sPtr[ 0 ] ); /* use putchar to display character */

You could also use *sPtr for sPtr[0].

 

[Eric Sosman]

yes, it should be Deitel and Deitel.
my computer corrected the spelling.

Ahh, good old computers! What would we do without them?

/* Fig. 8.13: fig08_13.c
Using gets and putchar */

Aside: The code actually uses fgets(), not gets(). That's

#include <stdio.h>

void reverse( const char * const sPtr ); /* prototype */ 6

int main( void )
{
char sentence[ 80 ]; /* create char array */
printf( "Enter a line of text:\n" ); 12

"12"?

that was a line number. it there do to my editing effort.

For future reference: When you post code that's giving you
trouble, post *exactly* the troublesome code. Don't re-type it,
don't paraphrase it, copy and paste directly from your code editor.
That way you'll be spared the embarrassment of posting some silly
typo and reading forty-leven replies that point it out instead of
addressing the actual problem. "We can't debug what we can't see,"
so make sure we see what needs debugging and not something else.

fgets ( sentence, 80, stdin );


The chapter is about: "Standard Input/Output Library Function"

so, i think it's more about showing the use of the functions,
but thanks for the incite of correct usage.

fibonacci is discussed, but i understood the code there.

Is this like pushing these characters onto a stack?
so, as i work down the stack the next line is executed, the putchar()?

Sort of. It may be more useful to think of it as pushing a
"state" or "situation" on a stack. In the recursive call, you're
saying "Go off and perform your sub-task, then come back *here*
and I'll take care of the rest." Each stack entry is a "*here*",
a "Now, then, where was I?" to be resumed after solving the sub-
problem.

my thought was that it actually move down the string of characters one character at
a time, i mean ...

let's say sentence is "abc\0" (following Paul"s thought, he's right it's shorter)

I liked Paul N's response: Direct and to the point.

so
when reverse is called
sPtr->abc\0
the else statements are executed
so reverse is called (starting at the address of the second char)
sPtr -> bc\0
the else statements are executed
so reverse is called
sPtr -> c\0
the else statements are executed
so reverse is called
sPtr ->\0
now this the base case so we work back down the stack
( i may not be using terminology stack correctly here)

moving back down (so to speak)
sPtr[0] ->c so execute putchar[sPtr[0]) that prints c
still moving back down
sPtr-> b so execute putchar ... that prints b
still moving back down
sPtr-> a so execute putchar ... that print a

cba

ok that said, that would mean that when a recursive function is called
as it works it way back, after it's base case has been found it should start
execution where it left off which would be after the recursive() call.

Does that make sense?

Yes, that's exactly It. No different from an ordinary function
call, really: You say "Computer! Go compute this square root, then
come back *here* with the answer" -- and the computer remembers where
"*here*" is, so it knows where to resume after the square root is
found. This is exactly what happens in a recursive call, too, the
only mind-bending part being that the function calls itself, and when
the inner call finishes it resumes where it was called from -- which
is, once again, in itself.

Well, when a function assigned to perform Job X calls itself,
isn't that an infinite loop? Yes, it could be -- of course, your
computer would run out of memory to store an infinite number of
"*here*" places where it should resume, so the infinite loop would
be cut short by the computer's finite resources. But in a
"practical" recursion the function told to do X does not call
itself to do X, but to do some smaller sub-task X.1 (or set of
sub-tasks X.1, X.2, ...) Eventually you arrive at a "base case"
where task X.1.3...1 is "small enough" to be solved directly without
further recursion. The lowest-level invocation solves its sub-sub-
sub-problem and returns to "*here*" in the calling invocation,
exactly as if it had provided a square root for a caller that's
solving a quadratic.

At a theoretical level, recursion and iteration are equivalent:
Any loop can be expressed as a recursion, any recursion can be
expressed as a loop. The choice of which "framework" to use should
be driven by the nature of the problem and by the capabilities of
the programming language. As I wrote earlier, reversing a string
in C does not strike me as a problem best suited for a recursive
approach -- still, it *can* be done, and if it helps you understand
recursion without dragging in a bunch of topics you neither know nor
care about, that's all to the good.

 

[gdotone]

Well, when a function assigned to perform Job X calls itself,
isn't that an infinite loop? Yes, it could be -- of course, your
computer would run out of memory to store an infinite number of
"*here*" places where it should resume, so the infinite loop would
be cut short by the computer's finite resources. But in a
"practical" recursion the function told to do X does not call
itself to do X, but to do some smaller sub-task X.1 (or set of
sub-tasks X.1, X.2, ...) Eventually you arrive at a "base case"
where task X.1.3...1 is "small enough" to be solved directly without
further recursion. The lowest-level invocation solves its sub-sub-
sub-problem and returns to "*here*" in the calling invocation,
exactly as if it had provided a square root for a caller that's
solving a quadratic.

your explanation was exactly what i needed to drive the point home.
of course, the function call, recursive though it is, would then come
back to the point in the program after the function left off and
continue its work. man! i don't know how that point blew by me. Thanks for
the patient explanation.

in the fibonacci example, in the text, there is no code after the function call.

I think i've got it, now. plus using a string to do this, recursion, may have helped to
throw me for a loop.

your explanation makes absolute sense.

At a theoretical level, recursion and iteration are equivalent:
Any loop can be expressed as a recursion, any recursion can be
expressed as a loop. The choice of which "framework" to use should
be driven by the nature of the problem and by the capabilities of
the programming language. As I wrote earlier, reversing a string
in C does not strike me as a problem best suited for a recursive
approach -- still, it *can* be done, and if it helps you understand
recursion without dragging in a bunch of topics you neither know nor
care about, that's all to the good.

I'm going to look for some exercises that require recursion so i can
practice the idea. (when to use recursion...the problems that lend themselves to
recursion and changing recursion to iteration)

Thanks Eric, perfect explanation for me...

g.

 

[Hans Vlems]

Op zondag 8 september 2013 22:41:04 UTC+2 schreef (e-mail address removed):

From Dietel and Dietel

[snip]

Let the sentence be Hello.

I get back olleH.



When is putchar called.



Thanks,



g.

Perhaps this simplified version of reverse will help you:

void reverse(const char * const sPtr)
{
if (sPtr[0]) reverse(&sPtr[1]);
putchar(sPtr[0]);
}

Hans

 

[Hans Vlems]

Op maandag 9 september 2013 12:37:41 UTC+2 schreef Richard Damon:

Perhaps this simplified version of reverse will help you:
void reverse(const char * const sPtr)

{

if (sPtr[0]) reverse(&sPtr[1]);

putchar(sPtr[0]);

}

Hans

The one problem is that this code is significantly different then the

original, and has a bug introduced (you are going to output the null

that was at the end of the string out first). If you are going to

rewrite it, is should be like:



void reverse(const char * const sPtr)

{

if (sPtr[0])

{

reverse(&sPtr[1]);

putchar(sPtr[0]);

}

}





but I don't think this would help that much in the comprehension of the

recursion, if the problem was not understanding how recursive calls work

(being exactly the same as non-recursive calls).

Of course the code is different, otherwise it wouldn't help at all.
The point was to simplify the recursion method and possibly assist in understanding the technique.

 

[blmblm]

On 9/8/2013 4:41 PM, (e-mail address removed) wrote:

[ snip ]

/* recursively outputs characters in string in reverse order */
void reverse( const char * const sPtr )
{
/* if end of the string */
if ( sPtr[ 0 ] == '\0' ) { /* base case */

This might become

if (sPtr[0] == '\n' || sPtr[0] == '\0')

return;
} /* end if */
else { /* if not end of the string */
reverse( &sPtr[ 1 ] ); /* recursion step */
putchar( sPtr[ 0 ] ); /* use putchar to display character */
} /* end else */

} /* end function reverse */

[ snip ]

Aside: Reversing a string isn't a problem that really calls
out for a recursive solution; an iterative method would be much
more direct. I suppose D&D are using it not as a way to reverse
a string, but as a way to introduce recursion without tying the
student up in a lot of complications -- I have to admit it's a
better problem than the usual Truly Awful exercise of computing
Fibonacci numbers! Still, the typical reason for a recursive
approach is when the "splitting" step produces two or more sub-
problems to be solved recursively. Exploring a maze, for example:

void explore (Junction junction) {
// Here I am at a junction where N corridors branch
for (int i = 0; i < junction.corridorCount; ++i) {
Corridor corridor = junction.corridor;
if (! corridor.explored) {
corridor.explored = true;
explore (corridor.junctionAtOppositeEnd);
}
}
}

The sub-problems are to explore the maze starting from the other
end of each of the N branching corridors; the "super-problem" is
to explore the maze starting from `junction'. Now to explore
the entire (connected portion of) the maze, just clear all the
`explored' flags and call explore(anyJunctionYouCareToStartFrom);
the recursion will follow all possible leads from that point on.

I'll agree that the usefulness of recursion is (often?) better
illustrated by problems in which the solution is generated using
more than one recursive call, your example being one such.


But the example quoted by the OP .... An iterative solution is
indeed more direct. However, one can use recursion to avoid the
maybe-problem of deciding how big to make the buffer for fgets(),
as shown in the revision below.

(Not an original idea, but one I thought was clever when it was first
shown to me some years ago.)

One might reasonably claim that the overhead incurred by recursion
easily swamps any advantage, but still -- kind of clever?


#include <stdio.h>

/*
* read characters until end-of-line and print in reverse order
* does not print end-of-line
*/
void reverse(void) {
int ch;
if ((ch = getchar()) != '\n') {
reverse();
putchar(ch);
}
}

int main(void) {
printf("enter a line of text:\n");
printf("reversed:\n");
reverse();
putchar('\n');
return 0;
}

 

[Malcolm McLean]

On 9/8/2013 7:15 PM, (e-mail address removed) wrote:

At a theoretical level, recursion and iteration are equivalent:
Any loop can be expressed as a recursion, any recursion can be
expressed as a loop. The choice of which "framework" to use should
be driven by the nature of the problem and by the capabilities of
the programming language. As I wrote earlier, reversing a string
in C does not strike me as a problem best suited for a recursive
approach -- still, it *can* be done, and if it helps you understand
recursion without dragging in a bunch of topics you neither know nor
care about, that's all to the good.

There's something called the lambda calculus which is theoretically very
important - basically all possible calculations can be done by passing
true or nil arguments to a recursive function which uses the parameters
as state. But it's not of much use for practical, everyday programming.

In C and most procedural languages, recursion is mainly used when operating
on data which is tree-like. Trees arise all the time, both in obvious
contexts like directories or genealogies, and in the less obvious like
compression and expression parsing.

You can argue about whether it's best to teach recursion using a problem
where you'd normally use recursion for real, or on a problem where
you generally wouldn't, like string reversal.

 

[James Kuyper]

Note: Google Groups has a defect that Google is unwilling to fix, which
causes quoted material to be double-spaced. There are better news
readers out there, such as Mozilla Thunderbird, and good free news
servers that you can use with them, such as eternal-september.org.
However, if you insist on continuing to use Google Groups, please remove
the spurious extra spacing it inserts in quoted material.

Op maandag 9 september 2013 12:37:41 UTC+2 schreef Richard Damon:

Perhaps this simplified version of reverse will help you:

void reverse(const char * const sPtr)
{
if (sPtr[0]) reverse(&sPtr[1]);
putchar(sPtr[0]);
}

....
The one problem is that this code is significantly different then the
original, and has a bug introduced (you are going to output the null
that was at the end of the string out first). If you are going to
rewrite it, is should be like:

void reverse(const char * const sPtr)
{
if (sPtr[0])
{
reverse(&sPtr[1]);
putchar(sPtr[0]);
}
}

but I don't think this would help that much in the comprehension of the
recursion, if the problem was not understanding how recursive calls work
(being exactly the same as non-recursive calls).

Of course the code is different, otherwise it wouldn't help at all.

The code wouldn't be helpful unless it attempts to print out the null
character that the original code correctly did not print out? I find
that claim confusing. Richard Damon's version seems to me to be much
more helpful than yours.

 

[glen herrmannsfeldt]

(snip)

In C and most procedural languages, recursion is mainly used
when operating on data which is tree-like. Trees arise all
the time, both in obvious contexts like directories or
genealogies, and in the less obvious like compression
and expression parsing.

Yes. For linear problems, such as linked lists, recursion is
rarely the best solution. Even for real recursive algorithms,
it is often more efficient, and not so much more work, to do
it without using recursive calls. Quicksort is a favorite
example.

You can argue about whether it's best to teach recursion using a
problem where you'd normally use recursion for real, or on
a problem where you generally wouldn't, like string reversal.

I suppose one should explain up front that the problems are just
examples. The favorite first recursion example is factorial, which
is much easier to implement as a loop. Fibonacci is horribly
inefficient as recursion, and easy to implement as a loop.

-- glen

 

[Paul N]

I suppose one should explain up front that the problems are just
examples. The favorite first recursion example is factorial, which
is much easier to implement as a loop. Fibonacci is horribly
inefficient as recursion, and easy to implement as a loop.

I think one snag with the string reversal shown is that the function calls itself straight away, diving down the nested calls and only doing the actual work on the way back up again. This is not the most intuitive way of doing things, and this may be part of what confused the OP.

 

[osmium]

:

<this weeks version of google atteempt to subvert Usenet>

I think one snag with the string reversal shown is that the function calls
itself straight away, diving down the nested calls and only doing the actual
work on the way back up again. This is not the most intuitive way of doing
things, and this may be part of what confused the OP.

 

[glen herrmannsfeldt]

(snip, I wrote)

I think one snag with the string reversal shown is that the
function calls itself straight away, diving down the nested
calls and only doing the actual work on the way back up again.
This is not the most intuitive way of doing things, and
this may be part of what confused the OP.

I suppose. One popular use for recursion is to deallocate a tree.

A linked list isn't hard to deallocate in order, remembering the
address for the next link while deallocating the current one.

For a tree, it is much easier to deallocate from the leaf back
to the root, so on the way back up, as you say. Just a little
less intuitive.

-- glen

 

[Ben Bacarisse]

(snip)


Yes. For linear problems, such as linked lists, recursion is
rarely the best solution.

.... in C. In languages that use it the basic control structure it
becomes quite natural to use it for linear solutions.

Even for real recursive algorithms,
it is often more efficient, and not so much more work, to do
it without using recursive calls. Quicksort is a favorite
example.

All loops are "real recursive algorithms", but not all recursive
patterns correspond to loops.

I suppose one should explain up front that the problems are just
examples. The favorite first recursion example is factorial, which
is much easier to implement as a loop. Fibonacci is horribly
inefficient as recursion, and easy to implement as a loop.

Not at all. You can implement a Fibonacci function using recursion that
is not horribly inefficient. You can do it even in C.

 

[Joe Pfeiffer]

Not at all. You can implement a Fibonacci function using recursion that
is not horribly inefficient. You can do it even in C.

I would be very surprised to see a recursive Fibonacci that is both
anywhere near as efficient as the obvious iterative solution and even
remotely near as clear as either the obvious iterative solution or the
obvious recursive solution.

 

[osmium]

Factorial is equally easy and clear as a loop or as recursion.

They will be equally clear *after* you home some basic understanding of
recursion. Recursion is, IMO, a pretty unnatural way of doing things. I
can't think of much in daily life or thought that is analogous to recursion.
The text book example is someone looking into a mirror which shows a second,
reflected mirror.

I agree that the Ackermann function is a good step for serious students of
recursion (but my interest is not that great).

 

[Malcolm McLean]

They will be equally clear *after* you home some basic understanding
of recursion. Recursion is, IMO, a pretty unnatural way of doing
things. I can't think of much in daily life or thought that is
analogous to recursion.

We're used to hierarchies. The Pope has cardinals below him who have bishops who have priests who have laypeople. So Pope is to cardinal
as bishop is to priest.