Difference between revisions of "Recursive Functions"
From Sutherland_wiki
(→Examples: Situations which can be solved with recursion) |
(→For the string 'racecar', the program would work like this:) |
||
| (7 intermediate revisions by the same user not shown) | |||
| Line 24: | Line 24: | ||
*Imagine a series of nested folders and files; folders have files and subfolders within them. Every single file needs to be opened. | *Imagine a series of nested folders and files; folders have files and subfolders within them. Every single file needs to be opened. | ||
| − | *You have a function, ''openerFunc'', which opens all the files in a specified folder. If folder A contains files and folders, you will want to use recursion. As you move down, ''openerFunc'' will open each file. Once a folder is hit (say folder B), '' | + | *You have a function, ''openerFunc'', which opens all the files in a specified folder. If folder A contains files and folders, you will want to use recursion. As you move down, ''openerFunc'' will open each file. Once a folder is hit (say folder B), ''openerFunc'' calls ''openerFunc'', telling itself to open the files in folder B. This is repeated every time a folder is encountered. Opening the nested subfolder is the simplifying step. Once a folder is found which contains only files, the recursive calls will stop. This is the base case. |
== Pseudo-code For ''palFinder'' == | == Pseudo-code For ''palFinder'' == | ||
| Line 30: | Line 30: | ||
''palFinder''(possiblePal) %a function that takes a string which could be a palindrome | ''palFinder''(possiblePal) %a function that takes a string which could be a palindrome | ||
| − | 1) firstLetter = first letter of possiblePal | + | 1) firstLetter = first letter of possiblePal |
| − | 2) lastLetter = last letter of possiblePal | + | 2) lastLetter = last letter of possiblePal |
3) '''if''': the first letter and the last letter are in the same position | 3) '''if''': the first letter and the last letter are in the same position | ||
| Line 40: | Line 40: | ||
4) '''if''': the first letter is equal to the last letter | 4) '''if''': the first letter is equal to the last letter | ||
| − | '''then''': | + | '''then''': possiblePal = a substring of possiblePal with the current first and last letters removed. Call palFinder(possiblePal) |
| − | |||
5) else: Exit program. Write to the screen that possiblePal is not a palindrome. | 5) else: Exit program. Write to the screen that possiblePal is not a palindrome. | ||
| − | ===For the string 'racecar' the program would work like this: === | + | ===For the string 'racecar', the program would work like this: === |
| − | * firstLetter = r, lastLetter =r | + | * firstLetter = r, lastLetter = r |
| − | * These two letters are not in the same position, so | + | * These two letters are not in the same position, so the program continues |
| − | * The firstLetter and the lastLetter are both r's, so | + | * The firstLetter and the lastLetter are both r's, so possiblePal is re-defined as 'aceca' |
* palFinder calls itself using 'aceca' as its argument | * palFinder calls itself using 'aceca' as its argument | ||
| − | * The firstLetter and the lastLetter are both a's (and they're not in the same location), so | + | * The firstLetter and the lastLetter are both a's (and they're not in the same location), so possiblePal becomes be 'cec' |
| + | * palFinder calls itself using 'cec' as its argument | ||
| + | * The firstLetter and the lastLetter are both c's (and they're not in the same location), so possiblePal becomes be 'e' | ||
* palFinder calls itself using 'e' as its argument | * palFinder calls itself using 'e' as its argument | ||
* The first letter and the last letter are the same e | * The first letter and the last letter are the same e | ||
* The program exits and reports that racecar is a palindrome | * The program exits and reports that racecar is a palindrome | ||
Latest revision as of 21:59, 26 August 2013
Contents
What is a recursive function?
Recursive functions are any functions which 'call' or 'use' themselves in order to move from the most complicated form of a problem to the simplest.
Anytime self-similarity is seen in a problem, a recursive solution will typically work nicely.
Components of Recursion
When using recursion, it's essential to have:
- A simplifying step. Recursion is used to trivialize a more complicated problem by breaking it into parts which can be solved with the same procedure.
- A base case. This is the simplest possible case. Once this case is reached, your program should stop calling itself.
Examples: Situations which can be solved with recursion
Palindrome Finder
- A palindrome is a word or phrase which can be read the same way backwards or forwards. 'racecar' and 'hannah' are two examples.
- To determine if a word is a palindrome, one would look at the first and last letter and check if they are the same. If they are, the second letter and the second to last letter should be checked. This should be repeated until the the ends meet. A recursive program, palFinder would begin by checking the outer letters. It would perform the simplifying step of moving one letter in on each side. palFinder can now be called to check these new letters. This is repeated until a single middle letter is reached, or until advancing positions causes the beginning and ending positions to cross. This is the base case.
Nested Folders
- Imagine a series of nested folders and files; folders have files and subfolders within them. Every single file needs to be opened.
- You have a function, openerFunc, which opens all the files in a specified folder. If folder A contains files and folders, you will want to use recursion. As you move down, openerFunc will open each file. Once a folder is hit (say folder B), openerFunc calls openerFunc, telling itself to open the files in folder B. This is repeated every time a folder is encountered. Opening the nested subfolder is the simplifying step. Once a folder is found which contains only files, the recursive calls will stop. This is the base case.
Pseudo-code For palFinder
palFinder(possiblePal) %a function that takes a string which could be a palindrome
1) firstLetter = first letter of possiblePal
2) lastLetter = last letter of possiblePal
3) if: the first letter and the last letter are in the same position
then: Exit program. Write to the screen the possiblePal is a palindrome.
4) if: the first letter is equal to the last letter
then: possiblePal = a substring of possiblePal with the current first and last letters removed. Call palFinder(possiblePal)
5) else: Exit program. Write to the screen that possiblePal is not a palindrome.
For the string 'racecar', the program would work like this:
- firstLetter = r, lastLetter = r
- These two letters are not in the same position, so the program continues
- The firstLetter and the lastLetter are both r's, so possiblePal is re-defined as 'aceca'
- palFinder calls itself using 'aceca' as its argument
- The firstLetter and the lastLetter are both a's (and they're not in the same location), so possiblePal becomes be 'cec'
- palFinder calls itself using 'cec' as its argument
- The firstLetter and the lastLetter are both c's (and they're not in the same location), so possiblePal becomes be 'e'
- palFinder calls itself using 'e' as its argument
- The first letter and the last letter are the same e
- The program exits and reports that racecar is a palindrome
