INFO1110 Lecture Notes - Lecture 12: Recurrence Relation

• School: University of Sydney
• Department: Information Technology
• Course: INFO1110
• Professor: John Stavrakakis

Document Summary

Recursion is based on solving problems in terms of solutions to simpler problems. A problem can be solved with recursion if an arbitrarily-sized problem can be solved by first solving a smaller version of that problem, reducing it to smaller and smaller problems until we get a trivial solution. A function that calls itself is known as a recursive function. Every time the function is called, a new copy of it is loaded into memory with its own copies of local variables and arguments. Ingredients of recursion: a base case (the smallest problem/somewhere to stop) Known as the trivial case and is where we don"t need to use the recurrence relation to get the answer: the recurrence relation (a way to continue) Tells you how to get form a more complex case to a simpler one. You must: know what the recurrence relation and the base cases are, check whether the base case has been reached.