### What is Recursion?

#### WHAT IS RECURSION???

`From ggrotz@internetland.net Mon Mar 31 03:58:08 1997Newsgroups: comp.lang.pascal.borland,comp.lang.misc,comp.lang.pascal.miscSubject: Re: WHAT IS RECURSION???From: ggrotz@internetland.net (Programmer Dude)Date: Mon, 31 Mar 1997 01:58:08 GMTOn 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 GrotzingerRecursion=========Recursion, to put it simply, is the execution of a function orprocedure directly within that same function or procedure.  It ishard, sometimes, logically to see use of recursion, but when you see athoroughly repetitive action, recursion could be used.Recursion should be used with a procedure which basically has a smallnumber or NO parameters, since the recursion places a new occurrenceof the procedure on the stack, along with those variables.  It isquite possible for a procedure to recurse itself upwards of thousandsof times. Therefore, you could easily run out of memory in the stackin running your program.Basically, in logic, recursion is the repetition of a procedure as aregular or irregular loop by calling the procedure inside of theprocedure, with some regulated terminating code.NOTE: Recursion must be done with relative caution in Pascal.  It isreally, REALLY easy to shoot oneself in the foot, literally, by useof recursion.  It has it's advantages, but since Pascal is unlimitedby how, and why you use recursion, versus other languages, which maylimit 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 doesit...after that, I will explain the process in detail that goes behindhow it works.  It's a simple, elegant one line set of code in afunction that does all the multiplications for any number we put inthere.I will try my best to explain what exactly is going on here in thisexample of recursion.  That, I find, is the hardest thing to see inthe concept of how recursion works, is because it is hard toconceptualize how the variables and functions work, in a manner thatis understandable.In all of the books I have read, I have not seen an adequatedescription of the actual logic and action of recursion -- enough toallow people to understand the idea of what is going on.  Mostteachers I've heard of and talked to, just say what I have alreadysaid to this point, and shy away from actually requiring written codeusing recursion, or explaining code using recursion to enable peopleto truly understand what is going on.I seek to change those observed facts, by trying to fully explain thisexample below, so people may be able to understand them sufficiently.I hope this explanation could be the best people have ever seen, andI *definitely* want e-mail and feedback on how well I do in explainingthe concepts of what is going on (via showing all variable changes atall points, and order of execution of the code), because it is one ofthe hardest concepts in programming that I have come across inunderstanding.  (I will also ask for input like this in the part Iwrite 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 functionfactorial with regard to the variables, the biggest problem, I think,with understanding recursion -- if you don't understand the main bodyof the program, something is definitely wrong with you! :>  Line #'sare 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, whymemory (stack space allocated for procedure and functionsspecifically) runs out quick, and why I say to keep the parameters andlocal variables for that matter to a minimum....Recursion can be used in procedures, as well as functions, for anyrepetitive action.  They are just like the function call above, whichrecursed when or until an action became true.To be able to extend for example, the part 8 dir clone to list andsearch for files (list all files in all dirs), we would need to addanother boolean variable to get permission to run through all dirsencountered. We can re-call the directory list procedure with aregulating if variable of it being a directory.For more practice (I won't post the solution for these ones), you maywish to do this.  As another practice, you may wish to try and recodean integer power function (the "simplistic" power function) that Iincluded in my solution to part 7's programming problem to userecursion.Practice Programming Problem #13================================Code a program in Pascal and entirely Pascal that will make a catalogof the additive size of all files in all dirs on a drive specified onthe 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 sizeof the files on the drive.  You may use the function offered by theDOS unit to check yourself in your addition.2) The spacing is not exact above.  Make it look SIMILIAR to what Ihave above, but make it reasonably attractive...3) Use a forward.4) Be sure to check to be sure the drive is specified EXACTLY likeabove.5) Please use recursion for going through the drive (actually,recursion is probably the best way to do this).  But, be sure you putthe directories in the order listed above.6) Sizes of subdirectories are not counted in the size of a maindirectory.7) Be sure to error-check the command-line.Glenn GrotzingerWeb Page: http://www.geocities.com/Paris/3537Writer 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.`