Summary of Recursion (For week 7)

  I've talked a lot about recursion in my previous posts, but I never wrote something dedicate directly to recursion. And also, I believe Recursion is the one of the important cores of the whole course, which is the reason why I choose to summarize recursion.

_________________________________________________________________________________

  One way to describe repetition within a computer program is the use of loops, such as while-loop and for-loop constructs. Recursion is an entirely different and new way to achieve repetition.
  First of all, I'd like to talk about what is recursion.  Recursion is a technique "by which a function makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation.[1]" Recursion provides an elegant and powerful alternative for performing repetition tasks.  So secondly, I want to talk about the fundamental pattern of writing recursive functions:

         ●Step 1 Setting a general and easiest base case which does not need recursion. For example, for the most of the time, in a tree, the first step is assuming that the tree has only one node(which is also the root).
         ●Step2  Figuring solutions out in more complicated cases that require using recursion. This recursive function will continue call it self until it reaches to base case and then starts from the next element and call it self again and again. This whole process ends as long as all the elements of the origin object are executed by the function. One of most important thing is that yo set your base case correctly, otherwise the loop would be infinite.
         ●Step3 I think step 3 is optional. Sometimes we could compact our codes into one line instead of using "if...: .....    else: ....." this kind of form. For instance we could use ternary if to make our codes concise.

  To sum up, the point of writing recursion is that breaking a problem down into small pieces -- base case(case that is simple enough) and more complicated case(general case).

   Thirdly, I want to talk about when to use recursion. I believe recursion is widely used in computer science. We learn a lot about Trees, for instance, binary search, calculating the hight and children of a tree or a subtree and so on. In addition, things like sorting algorithms also need recursion. 
   Basically, when you need the help of loop, however, for loop and while loop cannot solve this complex problem, then recursion is absolutely the best choice. Although I cannot deny that sometimes, compared with recursion, the thinking processes of for and while loop are easier, the codes of recursion are more clearer and more elegant.

   In a word, recursion is a good technique to solve problems, because it makes everything clearer and easier.


______________________________________


Reference:
[1] Data Structure and Algorithms in Python