Khan Academy: "Recursive Factorial Function" and "Fibonacci Numbers"

In these lectures we use Python, which is an easy-to-use procedural and object-oriented language, but our focus will not be on the syntax of the language. Rather, our focus is the concept of recursion, the requirements for the program (i.e., the statement of the problem), the design of the program, the semantics of the program (this is the stage in which we don't worry too much about the syntax of Python – knowing Java and C++ enables you to learn Python easily), and the verification of the program implementation (we do this by stepping through the program and running several test cases).

Note that the term verification refers to the correctness: the code running without errors and the code correctly implementing the design. Validation refers to the satisfaction of the requirements for the program: the requirements accurately reflecting problem or task the program is to perform, the design satisfying the requirements, and the code satisfying the requirements.

Computer science and programming have strong ties with mathematics, and recursion may remind you of a proof method in mathematics called mathematical induction, which is typically used when we want to prove a statement involving the natural numbers, i.e., "n". To prove the statement involving "n", we: 1) prove the statement for a base case, usually n = 1; 2) assume the statement is true for n-1; 3) then prove the statement for "n", using steps 1 and 2. So, get started by watching the first video, which gives the requirements for the program to be written.

Now watch the second lecture, which uses an iterative design to satisfy the requirements. Remember that this subunit is on recursion. So why do we look at iteration? We use an iterative example to help us better understand recursion, to show that requirements (or programming problems) can have several program implementations, and to enable you to compare iteration and recursion. This design makes use of a list data structure. After implementing an iterative design, (that is, writing the program), Khan runs it to demonstrate that it works correctly for several test cases.


Next, watch the third lecture, which presents some verification of the iterative design by stepping through the program implementation, line by line and variable by variable.


Next, watch the fourth lecture, which now uses a recursive design to satisfy the requirements. This recursive implementation uses a string data structure to print out the successive calls of the function to itself. This recursive implementation is tested using several inputs. Note that the calls show that the call for "n" makes use of the call for "n-1", etc. (i.e., the mathematical inductive step 2 above).

You should compare this recursive implementation with the iterative implementation. If you have to find a series of natural numbers, and you are given the first on or two (called the base cases) as well as the rule for calculating the next integer in the series, you can apply the rule sequentially, finding the third, the fourth, the fifth, etc., until you find the nth. A program that implements this 'manual' approach is the iterative program.

Another approach assumes that we can express the rule as a formula. For example, the nth term = (n-1)st term + (n-2)nd term; this can be expanded to, nth term = (n-2)nd term + 2* (n-3)rd term + (n-4)th term; and this expansion can be continued to result in as many terms as needed to give an expression that calculates the nth term. To find the nth term, all you would have to do is enter the base cases into the formula and do one calculation (no iterating). The recursive function, in effect, does this. The general formula is programmed: fibonacci (n) = fibonacci (n-1) + fibonacci (n-2). This general recursive formula is 'automatically' calculated for us by the interpreter. The interpreter uses an internal data structure, a stack, to implicitly calculate the formula by "iterating" through the stack- i.e., the interpreter does the iteration for us.


Finally, watch the last lectures, which present some verification of the design and implementation by stepping through the program, line by line and function call by function call. We say "some" because there are other verification techniques that can be used, depending on how much assurance is needed for correct execution of the program to satisfy various users and various needs.

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Last modified: Tuesday, October 15, 2019, 12:04 PM