GT AE 6382 - AE 6382 Recursive Programming

Unformatted text preview:

Recursive ProgrammingRecursion in ProgrammingWhat is RecursionRecursion in FunctionsWhy Program Recursively?Recursion vs IterationHow to Program RecursivelyFactorial ExampleSlide 9Tracing the Recursive ExampleTracing the Recursive Example (cont’d)GraphicallyExampleExample: Series SummationExample: Series Summation (2)Example: Series Summation (3)Example: Summing the DigitsExample: Summing the Digits CodeExample: Summing the Digits Code – cont’dExample: Greatest Common DenominatorExample: GCD CodeExample: Adaptive Linear InterpolationExample: Adaptive Linear Interpolation (2)Example: Adaptive Linear Interpolation (3)Example: Cumulative File Size in DirectoryExample: Cumulative File Size in Directory (2)Fall 2006AE6382 Design Computing 1Recursive ProgrammingUnderstand the potential value of recursive programmingKnow how to program a recursive functionUnderstand how a recursive call is executedBe able to trace a recursive function.OBJECTIVESThis is your brain on recursionFall 2006AE6382 Design Computing 2Recursion in Programming•Objectives of this lecture are:•What is Recursion?•Why is Recursion useful?•How to program recursively?•Examples–Factorial–Iterative vs recursive?–Counting sum of digits–Greatest Common DenominatorFall 2006AE6382 Design Computing 3What is Recursion•IN MATH iteration and recurrence relations are used: –Iteration is the process by which something is calculated in successive steps: ex=1+x+x2/2+x3/6+…xn/n! where each term adds smaller and smaller amount to the sum (converges).–Recursion (or a recurrence relation) is the process of defining a function in terms of a simpler version of itself. Examples are: N!=N(N-1)! or Jp+1(x)=(2p/x)Jp(x)-Jp-1(x)•IN COMPUTER SCIENCE: Recursion is the process of successively breaking a problem into smaller parts where each is a smaller/simpler version of the previous until a simple solution is reached. Back-substitution then leads to the solution for the original problem.Fall 2006AE6382 Design Computing 4Recursion in Functions•A recursive function is a function that calls itself in the course of computing its result. For example:–Factorial: N! = N (N-1)! is a recursion– but cos(cos(x) is not a recursion•Most recursive or iterative math procedures can be coded with loops. Some languages like Matlab, C and Java support recursive functions.Fall 2006AE6382 Design Computing 5Why Program Recursively?Recursive Code Non-Recursive• Code typically has fewer lines.• Code can be conceptually simpler, depending on your perspective• Often easier to maintain!• Code is longer.• Code executes faster, depending on hardware and programming language.Fall 2006AE6382 Design Computing 6Recursion vs Iteration•Recursion and iteration are close "cousins" and sometimes it is hard to decide…•Iteration:Usually involves program looping using for or while statements•Recursion:Breaks out a simple part of the problem and then calls itself to solve the remaining part. Usually involves use of if-else statements to determine when the simplest remaining part is reached.Fall 2006AE6382 Design Computing 7How to Program RecursivelyTYPICAL RECURSIVE CODE LOOKS LIKE THIS:function [y]=f(x)if (condition that determines stopping point) % calculate limiting value of function y=some limiting number;else % break problem into two simpler parts; % this will ultimately involve the % recursive call like the one below y=b*f(a*x)endFall 2006AE6382 Design Computing 8Factorial ExampleA RECURSIVE version code to compute this looks like:function fact=myfact(n)% This function calculates the factorial% using recursion and the definition:% n!=n*(n-1)!% Calculate limiting value of factorialif n==0 fact=1;else% Break into two simpler parts and then calculate% the value by calling the function again % (recursively): fact=n*myfact(n-1);endFall 2006AE6382 Design Computing 9Factorial ExampleAn ITERATIVE version of this code looks like:function fact=myfact(n)% This function calculates the factorial using a FOR loop% initialize output value to 1fact=1% Multiply output value fact succesively from 2 to n to% calculate factorial. In Matlab loop will be skipped% for n=1 or 0 so correct value will be returnedfor k=2:n fact=fact*k;endFall 2006AE6382 Design Computing 10Tracing the Recursive Example•Let’s run through an example to see what is going on. Assume n=2:–The function is called with n = 2 and it goes to the else statement, and calls myfact(1)•The first call to myfact is suspended while myfact(1) is called–When myfact(1) is executed (n=1), it again goes to the else statement and calls myfact(0)•The second call to myfact is suspended while myfact(0) is called–Finally, myfact(0) stops at the if and returns 1•This is the bottom of the recursion…Fall 2006AE6382 Design Computing 11Tracing the Recursive Example (cont’d)–The result (1) returned from myfact(0) is used in myfact(1): •fact = 1*myfact(0) = 1*1 = 1–The result (1) returned from myfact(1) is next used in myfact(2):•fact = 2*myfact(1) = 2*1 = 2–At this point, we are back to the beginning of the recursion and myfact(2) = 2•Note that as the recursion progresses, higher level instances of the function are suspended while lower levels execute. This can use lots of memory and take time but it is simple code!Fall 2006AE6382 Design Computing 12GraphicallySTARTmyfact(2)calls myfact(0)calls myfact(1)myfact(0) 1myfact(1)=1*myfact(0) 1myfact(2)=2*myfact(1) 2Returns the function resultfact = myfact(2)suspendssuspendssuspendscompletesFall 2006AE6382 Design Computing 13Examplefunction iforgot(n)% Simple example that looks a lot like iteration...if nargin==0, n=20, end; % in case no argument suppliedif n>1 disp('I will remember to do my homework.') iforgot(n-1)else disp('Maybe NOT!') % bottom of recursionend>> iforgot(5)I will remember to do my homework.I will remember to do my homework.I will remember to do my homework.I will remember to do my homework.Maybe NOT!Looks a lot like iteration…Fall 2006AE6382 Design Computing 14Example: Series Summation•One way to look at recursion is as iteration in reverse…•Consider a series summation:–The usual approach is to construct an iteration to compute partial sums starting with the first term and progressing to the last term11 2( ) sin cos( )2 2Nkkf x k xkppp=� �= +� �� ��Fall 2006AE6382 Design Computing 15Example: Series Summation (2)•Here’s


View Full Document

GT AE 6382 - AE 6382 Recursive Programming

Download AE 6382 Recursive Programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view AE 6382 Recursive Programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view AE 6382 Recursive Programming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?