Recursion: LinkedList, MergeSort, QuickSort, Tree, Backtracking

[YuezhenQin]

Recursion is a problem solving method. In code, recursion is implemented using a function that calls itself. Each function call stores its own variables, as the solution of a problem, pass it to build up a solution of the actual size of the problem.

1. We need what is called a base case to make the recursion stop. The base cases are conditions at the start of recursive functions that terminate the calls.

   All function calls break problems down towards base case. If you don’t have a proper stop or exit condition, you will get a StackOverflowException.

2. We also need what is called a recurrence relation - it's an equation that connects the terms together.

By combining the base cases and the recurrence relation, we can solve the subproblems and use those solutions to solve the original problem.

人通常是喜欢从前到后顺着想问题，不喜欢反过来从后往前思考；喜欢做加法、乘法，不喜欢做减法、除法；喜欢从小到大看，从下往上归纳，而不喜欢从大往小看，从上往下演绎。有些很简单的问题，正向思维难以找到答案，而逆向思维却马上迎刃而解。人的思维很多时候与计算机科学与技术应有的思维是矛盾的，要成为一流的计算机科学或工程师，需要有意识的改变自己的思维方式，突破常规。

[YuezhenQin]

Repetition: Recursion and Iteration

The opposite of a recursive algorithm would be an iterative algorithm. There is a branch of study that proves that any iterative algorithm can be written recursively. While iterative algorithms use for loops and while loops to simulate repetition, recursive algorithms use function calls to simulate the same logic.

[YuezhenQin]

function fn(i):

1. if i > 3:

2. return

3. print(i)

4. fn(i + 1)

5. print(f"End of call where i = {i}")

6. return

fn(1)

[YuezhenQin]

If you ran this code, you would see the following in the output:

// 1 // 2 // 3 // End of call where i = 3 // End of call where i = 2 // End of call where i = 1

[YuezhenQin]

As you can see, the line where we print text is executed in reverse order. The original call fn(1) first prints 1, then calls to fn(2), which prints 2, then calls to fn(3), which prints 3, then calls to fn(4). Now, this is the important part: how recursion "moves" back "up". fn(4) triggers the base case, which returns. We are now back in the function call where i = 3 and line 4 has finished, so we move to the line 5 which prints "End of call where i = 3". Once that line runs, we move to the next line, which is a return. Now, we are back in the function call where i = 2 and line 4 line has finished, so again we move to the next line and print "End of the call where i = 2". This repeats until the original function call to fn(1) returns.

[YuezhenQin]

This printing example is pretty pointless - it's easier to use a for loop if you just want to print numbers. Where recursion shines is when you use it to break down a problem into "subproblems", whose solutions can then be combined to solve the original problem.