Assigned topic: Recursion.
At this point, i have had my first exposure to recursion, a powerful technique in computer programming.
According to wikipedia,
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)."
Simply put, recursion technique is seen when the function being run calls itself within its own code (because the function calls itself to start its work again on the given input).
The following code illustrates an example of recursion (stolen from week 4 lecture slides):
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
This function sorts through a given list input and returns the greatest value within the list.
The most important component of any recursive call is its "base case." This is the condition in which the function has to reach so that it terminates and stops running. Otherwise, python will return a "recursion exceeds maximum depth" error.
The closest analogy that comes to my mind is the concept of a "while loop," because it is also an iteration technique that keeps running and running until it reaches a condition in which it stops. Likewise, the while loop faces the same problem of an "infinite loop" if its exit condition is not well defined.
So, it begs the question, what is the point of recursion when there already exists a similar technique that does the same job?
Refer to the rec_max(L) function above.
If the given input is a list of [1, 2, 3, 4, 5], the function would return 5. A very simple test case which either the for loop or while loop can easily accomplish.
However, what if the given input is something like: [1, [2, 3, 4], 5]?
A for loop, for example, would iterate through: 1, the inner list, then 5, and return 5, with no regard for the content of the inner list - for its assigned objective does not directly deal with such a disposition.
Even if you were to install a command to the effect of "if you encounter another list, start the iteration again," it is still not going to account for an input which has 99 layers (an exaggerated point) of nested lists.
This is where recursion comes in.
the 1 line code above in english means "if you encounter another list, start the iteration again." The code re-executes itself given the condition is met. In the example of the nested list, the only (known) way to dealing with an ADT that contains layers and layers of variables is to start the count again, as if you were to do it manually.
This is where recursion becomes indispensable: when the input ADT consists of entries that are not of the same format.
Recursion, at its base definition, is a form of loop. A loop is a command to the computer to execute code over and over again until the condition is met. However, recursion allows itself to start the iteration again if it becomes necessary. But, in general, a recursion should always be used when a big problem needs to be broken down into small problems and solved step by step. ex. decomposing a big list into smaller lists and iterating through each item to return the desired entry.
In brief, recursion is a powerful tool in computer science that allows the computer to solve complicated problems by breaking it down into smaller ones via. starting the iteration again - very useful when the given input ADT is not of a consistent format.
Friday, 28 February 2014
Thursday, 13 February 2014
week of february 12, 2014 csc148h1 winter 2014
This week was tough, >10 hour spent finishing up a1.
This is the first time in this course i have been implementing recursion, and i have implement it in two ways:
1) using recursion to calculate i, the integer constant 1<=i<n in the M(n) function. M(n) is function that generates the number of moves needed to finish a stool of n cheeses. There is always an i that minimizes the number of moves you need to make. What i did was that i used a for loop to iterate i 1<i<n and plugged into the M(n) equation. The M(n) values are then appended into an empty list. Then the appendix of the list is returned to produce i. I feel almost a little proud because they say that this is the hardest part of the assignment and i finished this function in <20 minutes.Most people tried to return --- in 1 line, but that was simply too complicated for python to operate. Instead, i created a helper function to be called within my main function, and that worked without bugs.
2) the second implementation of recursion was a bit unlike to what i understand recursion to be. if number of cheeses > 1, the order of the stools of the parameters in the move function are shuffled in different orders. again, like M(n), i called a 3-stool move function within my 4-stool move function, this is because when there are cheeses on the intermediate stool, there are only 3 stools you can use to work with (the origin stool is being occupied by the longer cheeses). The greatest challenge of this part is working with parameters i have not defined, tracing through where the recursion is working on, and coming up with a complete algorithm that moves the cheeses when moved over and over again.
All in all, i feel very accomplished that i have learned how to adequately implement recursion, however i do hope that the test will not be as difficult. =(
This is the first time in this course i have been implementing recursion, and i have implement it in two ways:
1) using recursion to calculate i, the integer constant 1<=i<n in the M(n) function. M(n) is function that generates the number of moves needed to finish a stool of n cheeses. There is always an i that minimizes the number of moves you need to make. What i did was that i used a for loop to iterate i 1<i<n and plugged into the M(n) equation. The M(n) values are then appended into an empty list. Then the appendix of the list is returned to produce i. I feel almost a little proud because they say that this is the hardest part of the assignment and i finished this function in <20 minutes.Most people tried to return --- in 1 line, but that was simply too complicated for python to operate. Instead, i created a helper function to be called within my main function, and that worked without bugs.
2) the second implementation of recursion was a bit unlike to what i understand recursion to be. if number of cheeses > 1, the order of the stools of the parameters in the move function are shuffled in different orders. again, like M(n), i called a 3-stool move function within my 4-stool move function, this is because when there are cheeses on the intermediate stool, there are only 3 stools you can use to work with (the origin stool is being occupied by the longer cheeses). The greatest challenge of this part is working with parameters i have not defined, tracing through where the recursion is working on, and coming up with a complete algorithm that moves the cheeses when moved over and over again.
All in all, i feel very accomplished that i have learned how to adequately implement recursion, however i do hope that the test will not be as difficult. =(
Sunday, 9 February 2014
week of February 5, 2014 csc148h1 winter 2014
This week, we were introduced to some applications of recursion and unit test.
By comparing lecture slides to our assignment 1, towers of anne hoy, it seems like our objective is to create an automated application that solves a problem by implementing recursion.
If all the instructions can be defined as a general formula instead of lines and lines of code on how to move cheeses around, the following can be an example of how such an application can be implemented:
1. move all but the bottom cheese to the source to intermediate stool.
2. move the bottom cheese from source to intermediate stool.
3. move all but the bottom cheese from the intermediate stool to the destination stool.
If all these commands are implemented into code as a base case, then calling the function again and again until it is done will create an automated "problem solver" to tower of anne hoy.
Unittest, on the other hand, is another form of automation. It provides a series of test cases to run to test the specific functions built within the test file, and executes them one by one and reports back the errors found. I tend of think of unittest as a general solution that can be used to test many different instances of the same code - input case, return result.
In brief, recursion and unittest are both powerful tools of automation that breaks down a long and complex task down to easy steps and implement until the job is done.
By comparing lecture slides to our assignment 1, towers of anne hoy, it seems like our objective is to create an automated application that solves a problem by implementing recursion.
If all the instructions can be defined as a general formula instead of lines and lines of code on how to move cheeses around, the following can be an example of how such an application can be implemented:
1. move all but the bottom cheese to the source to intermediate stool.
2. move the bottom cheese from source to intermediate stool.
3. move all but the bottom cheese from the intermediate stool to the destination stool.
If all these commands are implemented into code as a base case, then calling the function again and again until it is done will create an automated "problem solver" to tower of anne hoy.
Unittest, on the other hand, is another form of automation. It provides a series of test cases to run to test the specific functions built within the test file, and executes them one by one and reports back the errors found. I tend of think of unittest as a general solution that can be used to test many different instances of the same code - input case, return result.
In brief, recursion and unittest are both powerful tools of automation that breaks down a long and complex task down to easy steps and implement until the job is done.
week of january 29 2014 csc148h1 winter 2014
This week, we learned more about recursion.
The recursion technique carries out a job very much like the effect that a while loop does. A while loop, as covered in csc108, is a condition that is not met so that the sequence of code executes itself over and over again until either the condition is met or your computer run out of memory and crashes. The while loop learned and implemented in csc108 was a powerful tool in that it executes a large sequence of code repeatedly until the job is done. However, the implementation of the while loop has its flaws. Usually, the biggest problem a developer encounters during the implementation of a while loop is trying to determine, "will it run forever?" or "will it eventually stop?" Using a while loop, that is well-defined within its "while: ...." statement. Otherwise, if the while loop just keeps running and running, the code will crash and you could lose data.
The recursion technique, simply put, is given a base case, call the function within it self again and again until the base case is met. Recursion aims to solve problems where there are nested lists - lists within a list.
For example there is a list [0, 1, 2, [3[4,5,6]], 7], and you want to be able to iterate through every single element within every list, a while loop is not nearly as convenient as implementing recursion.
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
the function rec_max is called within the function itself and else is defined as the base case.
a seemingly intimidating technique, but definitely among the most powerful we will encounter in this course.
The recursion technique carries out a job very much like the effect that a while loop does. A while loop, as covered in csc108, is a condition that is not met so that the sequence of code executes itself over and over again until either the condition is met or your computer run out of memory and crashes. The while loop learned and implemented in csc108 was a powerful tool in that it executes a large sequence of code repeatedly until the job is done. However, the implementation of the while loop has its flaws. Usually, the biggest problem a developer encounters during the implementation of a while loop is trying to determine, "will it run forever?" or "will it eventually stop?" Using a while loop, that is well-defined within its "while: ...." statement. Otherwise, if the while loop just keeps running and running, the code will crash and you could lose data.
The recursion technique, simply put, is given a base case, call the function within it self again and again until the base case is met. Recursion aims to solve problems where there are nested lists - lists within a list.
For example there is a list [0, 1, 2, [3[4,5,6]], 7], and you want to be able to iterate through every single element within every list, a while loop is not nearly as convenient as implementing recursion.
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
the function rec_max is called within the function itself and else is defined as the base case.
a seemingly intimidating technique, but definitely among the most powerful we will encounter in this course.
Subscribe to:
Posts (Atom)