Basically, recursion is a programming strategy in which a particular problem is broken down into smaller sub-problems until the simplest possible solution is reached. There are three necessary components for a recursive problem to work; these include:
1) A base case. This is the simplest case possible to encounter in a recursive problem.
2) A recursive case. This is where the function calls itself.
3) A recursive case must be such that each call reduces the size of the problem, getting closer to the base case each time.
In programming, recursion can be achieved by having a function repeatedly call itself on an input - provided that each call reduces the size of the input itself. For example, say one wanted to calculate the product of two numbers, x=2 and y=3, without a multiplication sign. To approach the problem, we recall that xy is the same as adding the value x to itself y times. In other words, 2 x 3 is the same as 2 + 2 + 2.
Now, we write the recursive code (using the logic we have in the first paragraph), by analyzing the three points of recursion. In this case, the base case would be when y = 1; in other words we would return x. When y is greater than 1, we have the recursive case: we would want to add x to itself each time, while y decreased. The final code snippet for such would be:
def multiply(x, y):
if y == 1:
return x
else:
return x + multiply(x, y-1)
The result is that, as each iteration goes on, x would be added to itself until y reaches 1 in the recursive call; but by that time we would have added x y times, and that would be the final solution.
Recursion is an important tool, sometimes even easier to implement than the traditional iterative method, especially when we look at complex data structures such as binary trees, when we discover that the only way to traverse (or travel downwards) through a tree is by recursive calls on each node.
Ah, I have a lot of fond memories about recursion. In high school recursion was the one object that scared the heck out of my entire computer science class (save for a few people, Kashish and Ipsita) because they just simply could not understand the recursive process behind it. When we were first introduced to it in class, my teacher simply threw us into the formulation of a recursive problem - which was not helpful in any way, as he, despite being a great teacher and all, didn't really explain that well as to why the recursive process work. By the time the assignment for recursion had rolled in we were stumped (including me) and some people took the desperate measure of plagiarizing their work as a whole. Recursion was a problem.
Enter university, and the world of CSC148, where I was told that half of my code would have to be recursive. I had some fears about repeating the same frustration I had in high school with such a subject - until I met Danny Heap. After starting off the session with a lecture on tracing recursion, it soon dawned on me that the key to understanding recursion was code tracing; to understand how recursion worked in code, we needed to resolve the code ourselves as if we were the computer doing the problem. It makes sense; if we just tried to step into a recursive problem without understanding how a computer works on recursion, then we would end up in a deeper, more frustrating hole than we would have initially.
During the reading week, in preparation for assignment 2, I took it upon myself to do a couple of traditional recursion problems on my own, such as the factorial, palindrome, and math problems. For each problem, I would ask myself questions such as: "What is the base case?" "How would recursion work on each element of the problem?" "How can we reach the base case?" When I made a recursive call, before evaluating it I would trace the problem on my own to see whether the desired result would be achieved. Understanding how to trace recursion problems was the gold in the mine that helped me to comprehend recursive code solutions in class, labs, and in my personal coding endeavors.
Alas, thank you, Danny Heap, for making me a witness to the glories of writing recursive code.
No comments:
Post a Comment