Recursion
Recursion is the process of a subroutine calling itself.
Take a look at the program below. It is a program that will draw a tree.
The Main subroutine will ask you how big the tree should be, then it calls a subroutine called branch, and passes the size as an argument.
If you take a look at the subroutine 'branch' you will notice that it checks to see how long the branch is going to be. If the branch is larger than 6, it will draw half of the branch and then draw 2 new branches - calling itself for each new branch passing it a new smaller length as an argument. This is recursion!
If the branch is not greater than 6, it will draw a line of that length and stop. This must happen at some point or the subroutine will keep calling itself an infinite number of times (or at least until the computer runs out of memory).
Characteristics
A recursive subroutine must include the following elements:
A general case - whereby the subroutine will call itself
A Base case - a condition that will cause the subroutine to not call itself.
The base case must be reachable with a finite number of calls
Recursive Example: Factorials
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example...
5! = 5×4×3×2×1 = 120
The following Pseudocode show how we could solve the problem using recursion:
Each time the function is called, it pushes a new frame onto the stack - initialising new instances of the variables declared inside the subroutine.
When the function returns it’s value it pops off the stack allowing the previous function to continue with it’s instructions.
Challenge
Palindrome Checker
A palindrome is a word that is spelt the same forward as it is backwards, e.g. 'racecar'
Write a recursive function that when passed a string returns whether the string is a palindrome or not (True or False).
You know it's a palindrome if the outer two letters are the same and the inner letters are also a palindrome...
Key Words
Recursion
The process of a subroutine calling itself
Base Case
The case when a recursive subroutine does not need to call itself and will return to the previous stack frame
General Case
The case when a recursive subroutine makes a call to itself, and a new stack frame is created
Stack Frame
An instance of the subroutine that defines a new set of local variables and the return address from whence it was called.