WHAT IS RECURSION???
From ggrotz@internetland.net Mon Mar 31 03:58:08 1997
Newsgroups: comp.lang.pascal.borland,comp.lang.misc,comp.lang.pascal.misc
Subject: Re: WHAT IS RECURSION???
From: ggrotz@internetland.net (Programmer Dude)
Date: Mon, 31 Mar 1997 01:58:08 GMT
On Tue, 01 Apr 1997 19:22:02 GMT, posenj@lancet.co.za (Kevin Posen)
wrote:
>Uhh, like, what is 'recursion'???
From the Turbo Pascal for DOS Tutorial
by Glenn Grotzinger
Part 13: Recursion; system unit commands not covered yet.
copyright(c) 1995-96 by Glenn Grotzinger
Recursion
=========
Recursion, to put it simply, is the execution of a function or
procedure directly within that same function or procedure. It is
hard, sometimes, logically to see use of recursion, but when you see a
thoroughly repetitive action, recursion could be used.
Recursion should be used with a procedure which basically has a small
number or NO parameters, since the recursion places a new occurrence
of the procedure on the stack, along with those variables. It is
quite possible for a procedure to recurse itself upwards of thousands
of times. Therefore, you could easily run out of memory in the stack
in running your program.
Basically, in logic, recursion is the repetition of a procedure as a
regular or irregular loop by calling the procedure inside of the
procedure, with some regulated terminating code.
NOTE: Recursion must be done with relative caution in Pascal. It is
really, REALLY easy to shoot oneself in the foot, literally, by use
of recursion. It has it's advantages, but since Pascal is unlimited
by how, and why you use recursion, versus other languages, which may
limit it or not allow it all together.
As an example, we will look at taking a factorial of a number.
Basically, to use an example, 4! (factorial) is 4 X 3 X 2 X 1.
Algebraically, we could see a factorial (n!) as n X (n-1) X (n-2) X
(n-3)...(n - (n+1)). Let's try looking at a code example that does
it...after that, I will explain the process in detail that goes behind
how it works. It's a simple, elegant one line set of code in a
function that does all the multiplications for any number we put in
there.
I will try my best to explain what exactly is going on here in this
example of recursion. That, I find, is the hardest thing to see in
the concept of how recursion works, is because it is hard to
conceptualize how the variables and functions work, in a manner that
is understandable.
In all of the books I have read, I have not seen an adequate
description of the actual logic and action of recursion -- enough to
allow people to understand the idea of what is going on. Most
teachers I've heard of and talked to, just say what I have already
said to this point, and shy away from actually requiring written code
using recursion, or explaining code using recursion to enable people
to truly understand what is going on.
I seek to change those observed facts, by trying to fully explain this
example below, so people may be able to understand them sufficiently.
I hope this explanation could be the best people have ever seen, and
I *definitely* want e-mail and feedback on how well I do in explaining
the concepts of what is going on (via showing all variable changes at
all points, and order of execution of the code), because it is one of
the hardest concepts in programming that I have come across in
understanding. (I will also ask for input like this in the part I
write later on readdressing pointers)
program example_of_recursion;
function factorial(a: longint): longint;
var
c: longint;
begin
{1} c := 1;
{2} if a > 1 then {
{3} c := a * factorial(a-1);
{4} factorial := c;
end;
begin
writeln(factorial(4));
end.
to explain the path of logic in this program in calling the function
factorial with regard to the variables, the biggest problem, I think,
with understanding recursion -- if you don't understand the main body
of the program, something is definitely wrong with you! :> Line #'s
are placed in {}'s above this paragraph, and below this paragraph.
{ call to factorial }
{1} a = 4 c = 1
{2} 4 > 1 = true
{3} c = 4 * factorial(3);
{ call to factorial }
{1} a = 3 c = 1
{2} 3 > 1 = true
{3} c = 3 * factorial(2);
{ call to factorial }
{1} a = 2 c = 1
{2} 2 > 1 = true
{3} c = 2 * factorial(1);
{ call to factorial }
{1} a = 1 c = 1
{2} 1 > 1 = false (so the chain of calls ends...)
{3} skipped because 2 is false.
{4} c = 1; factorial function is 1.
{ end call to factorial }
{4} c = (2 * 1) = 2; factorial function is 2.
{ end call to factorial }
{4} c = (3 * 2) = 6; factorial function is 6.
{ end call to factorial }
{4} c = (4 * 6) = 24; factorial function is 24.
{ **FINAL** termination of factorial -- return of value 24 }
If you check the code, the final value is correct. 4! = 24.
Basically, with the layout I used, you can see especially also, why
memory (stack space allocated for procedure and functions
specifically) runs out quick, and why I say to keep the parameters and
local variables for that matter to a minimum....
Recursion can be used in procedures, as well as functions, for any
repetitive action. They are just like the function call above, which
recursed when or until an action became true.
To be able to extend for example, the part 8 dir clone to list and
search for files (list all files in all dirs), we would need to add
another boolean variable to get permission to run through all dirs
encountered. We can re-call the directory list procedure with a
regulating if variable of it being a directory.
For more practice (I won't post the solution for these ones), you may
wish to do this. As another practice, you may wish to try and recode
an integer power function (the "simplistic" power function) that I
included in my solution to part 7's programming problem to use
recursion.
Practice Programming Problem #13
================================
Code a program in Pascal and entirely Pascal that will make a catalog
of the additive size of all files in all dirs on a drive specified on
the command-line to a text file named FILESLST.TXT.
Sample output
-------------
c:\>sizelist c:
Drive: C
C: 131,123
C:\DOS 5,231,131
.. ...
C:\UTIL 3,212,985
C:\UTIL\ACAD 131,123
=============
527,212,122
Notes:
1) The additive end of the listing (under the ='s) is the total size
of the files on the drive. You may use the function offered by the
DOS unit to check yourself in your addition.
2) The spacing is not exact above. Make it look SIMILIAR to what I
have above, but make it reasonably attractive...
3) Use a forward.
4) Be sure to check to be sure the drive is specified EXACTLY like
above.
5) Please use recursion for going through the drive (actually,
recursion is probably the best way to do this). But, be sure you put
the directories in the order listed above.
6) Sizes of subdirectories are not counted in the size of a main
directory.
7) Be sure to error-check the command-line.
Glenn Grotzinger
Web Page: http://www.geocities.com/Paris/3537
Writer of the Excellent Training Manual known as the TP Tutorial.
To email, if you hit the reply button, delete the {remove_this}
out of the replied message.
