Some thoughts on recursion

It’s the fourth week of CSC148 and just a brief summary of what I have learnt: First week, object-oriented programming, the second week, inheritance and recursion, the third week, exception, and this week, more on recursion. Also, assignment 1 came out and it’s basically about the Hanoi tower with more than three pegs. Today, I am going to talk something about recursion. The most well-known recursive thinking, I believe, is the Fibonacci sequence – 1, 1, 2, 3, 5, 8…… Starting from the third number, each number is the sum of the two numbers before it.(5=2+3, 8 = 3+5) Every time we want a number, we need to know the two numbers before it, and to know the two numbers, we need to know the two numbers before themselves.  This may sound confusing, but it would be clearer when put into code.

The base case returns 1 when n equals 1 or 2 and if n is greater than 2, the program would firstly calculate the sum of the (n-1)th number and (n-2)th number, and to calculate the (n-1)th number, the program would calculate the sum of the (n-2) and (n-3)th number, and same for all the numbers until the program reaches base cases and return 1. Starting from 1, the program adds these numbers together and produces the nth number we want. As Danny said in class, tracing a recursive function could be too complex to handle, so my way of tracing the code is to use abstraction – Find patterns of the code for the first or two cases, then apply these patterns to more complex cases based on the assumption that the code could work properly.

As seen from the Fibonacci sequence program, through recursion, we can significantly reduce the length of the code. Through abstraction, recursion would be much easier to understand than writing in for loops or other loops. However, recursion, for most of the times, actually lowers the efficiency of the program. Thus, when using recursion, we need to find a balance between efficiency and code length – if the code could be converted into for loops while not extending much length, it is better not to use recursion. So analyze at the very beginning, and decide which way we are about to use.