Week 4

Main topic of week 4: recursive definition.

Recursion is a special naming processing, and it is similar to induction, which gives you a general body and a base on which the body will be built on. It is easy to define a recursive function, simply by control it's domain and range. But not all of the function are expressed good enough in recursive way, for example f(n) = f(n-1) surely is not a well defined recursive function, because there is no base case here to tell where the function should end.

Now, given a recursive function. we have a way to guess what the function will look like in closed form by a process called unwinding. Because the recursive way of def, the function can be substitute by it's child function, which makes the function approach to it's base. An interesting recursive function would be the Fibonacci sequence, in which not only one base case, but two of them, need to be provided. We often need to calculate the sum of the first n term of the function, for example, we need to remember the total number of rabbits raised before would be the sum of the Fibonacci sequence. Similarly, if a time complexity function is provided, we could use the sum of the function to indicate how many steps we need to complete on function.

In summary, we learnt recursive definition in this week and a powerful tool--"unwinding" to get closed form of recursive function, and how to find the time complexity function and complexity evaluation.