Recursive Functions

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