View source for 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), ''openFunc'' calls ''openerFunc'', telling it 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(_Inner)

2) lastLetter = last letter of possiblePal(_Inner)

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_Inner = a substring of possiblePal with the current first and last letters removed 
call palFinder(possiblePalInner)

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 we will continue
* The firstLetter and the lastLetter are both r's, so we let possiblePal_Inner be 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 we let possiblePal_Inner be cec
* 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