INB371 Week 6 Lecture

3 Pages
Unlock Document

Queensland University of Technology
Malcolm Corney

INB371 Lecture 5 Overview Recursion Recursive Algorithms Factorial Fibonacci Additive Sequences Recursion Recursion is a powerful problem solving strategy. Recursion involves reducing a large problem to smaller problems of the same form. If we’ve been tasked with distributing 1000000 pieces of junk mail, you couldn’t possibly doing it yourself. You could use a pyramid scheme, which lets people distribute to other people, and it keeps going down the chain. Having a function call itself is the principle behind recursion. A simple factorial mathematical function to multiply numbers from 1 to n. You could do it iteratively (in a for loop). Anything done iteratively can most likely be doing with recursion. If N = 0, the factorial function will return 1, and if it’s not zero, it will call itself until n reaches 0. Every time the function is called, a new stack frame is created, and any local variables and parameters that are defined in our main function is placed in the stack frame. As soon as the function is called in main, the parameter n gets passed with value 4. Once it reaches Factorial 0, it returns 1 to Factorial(1). This makes Factorial 1’s sum equal to 1 * 1. That returns 1 to Factorial 2, which the does 2 *1, sends 2 to factorial 3 which does 3 * 2, which is 6, etc. One of the problems with recursion is that if the recursion doesn’t stop, it will fill the stack with stack frames, and cause the program to crash due to running out of memory. When making recursive functions, you need to find the ‘simplest case’ to make it stop, for factorial that’ll be when n = 0. Fibonacci Sequence Fibonacci Sequence can be used as an example of recursion. If a fertile rabbit produces a new pair of offspring each month, rabbits become fertile in their second month. Because rabbits never die, and all rabbits from the previous month are still around, the number of fertile rabbit pairs is the number alive in the previous month, making the new value the sum of the previous two SEE CODE ON BLACKBOARD The calculation of Fibonacci sequence from this code causes the calculation to be extremely slow. This is due to the fact that using recursive functions for this means you have to make calls to an extremely large amount of functions, as Fib5 needs Fib4 and Fib3, and Fib4 needs Fib3 and 2, etc. This means that every level doubles the number of calculations. This means that it has a new efficiency class of O(2n). This is known as exponential efficiency, as the time taken to complete rises exponentially. Additive Sequences Fibonacci sequence comes from defining t0 = 0 and t1 = 1. We could model different population growth functions by changing these numbers. All of them use the same recurrence relation though. This means we can create a new function AdditiveSequence which has parameters t0, t1, and n. Because t1 in the second additivesequence call in a recursive stack is t0+t1, you simply pass t0+t1 in the t1 param in the next call. This essentially makes AdditiveSequence parameters hold the calculations al
More Less

Related notes for INB221

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.