CSC148 SLOG for week7

This week I want to make a summary of recursion(and I choose this topic to be graded, thanks).

What is recursion?

Briefly speaking, it’s a function calls itself. As we’ve learned in class, any problem solved by recursion can also be solved by iteration. However, using recursion is a wise choice for some complex problem since it always makes the code shorter.

A simple but representative example of recursion:

def recursion(n):

      if n == 1:

          return 1

      else:

          return n * recursion(n - 1)

It’s not difficult to find that this is a function for factorial. The function will automatically call itself until n equals 1 which stops the process of factorial. Since this question is not that hard, we can handle it using while loop, too. But when we facing a complicated question, we may need using loop under loop and, without doubt, it is more likely to make a mistakes. Using recursion, we just need to divide a problem into two parts, basic cases and sub-problems. Basic case is always zero or empty string/list(which is easy to solve) and for the sub-problems, the function calls itself until the basic case occurs. For example, we need recursion when writing functions with nested list. The function will run itself again if it encounter another list and stop when there is no more sub-list, solving the question layer by layer. So recursion is an essential tool for computer scientists when the problem involves an object within another object, such as some Trees question. 

Having eliminated the unnecessary code, recursion solves the most problems in an efficient and elegant way. Although it takes some time to grasp this brilliant method, you will find it’s all worthwhile after mastering it.