Class Notes (1,016,874)
CA (584,416)
U of S (3,517)
CMPT (50)
Lecture 11

# CMPT 115 Lecture Notes - Lecture 11: Linked List, Memory Address

14 pages31 viewsWinter 2016

Department
Computer Science
Course Code
CMPT 115
Professor
Jason Bowie
Lecture
11

This preview shows pages 1-3. to view the full 14 pages of the document.
Recursion Revisited
CMPT 115 lecture notes
Notes written by Michael Horsch, Mark Eramian, Ian McQuillan, Lingling Jin, and Dmytro Dyachuk
Objectives
After this topic, students are expected to
1. recognize recursive deﬁnitions and recursive algorithms
2. describe the general form of a recursive deﬁnition, as well as recursive algorithm.
3. identify the base case and general case for recursive algorithms
4. design recursive algorithms use the template for recursive algorithms
5. deﬁne the terms of activation records and system stack.
6. understand how recursion works in terms of activation records and the system stack.
7. analyze the time complexity of simple recursive algorithms.
Contents
1 Recursive Deﬁnitions 1
1.1 Introduction to Recursive Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Designing Recursive Algorithms 3
2.1 The structure of recursive functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 A template for recursive functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Examples ............................................... 5
2.4 Somehintsandrulesofthumb ................................... 8
2.5 Exercises ............................................... 8
3 How does recursion work? 10
3.1 "Local Memory": Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 TheSystemStack .......................................... 12
4.1 When should recursion be used in C++? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Time Complexity of Recursive Algorithms 14
1 Recursive Deﬁnitions
Recursion is a form of repetition based on function calls, instead of loops.
You may like loops better because you practice those more.
1

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

Recursion is easier than loops. Proof:
Recursion expresses a meaningful relationship.
Understanding relationships is what humans do best.
Therefore, recursion is what humans do best.
Q.E.D.
1.1 Introduction to Recursive Deﬁnitions
Recursion
Deﬁnitions that refer to themselves are said to be “recursive”.
Example:
n! = (1if n= 0 (base case)
n·(n1)! if n > 0(inductive step)
Suppose we re-formulate the !operation as a function:
factorial(n) = (1if n= 0
n·factorial(n1) if n > 0
It’s easy to re-formulate this as a recursive C++ algorithm.
Recursive Algorithms
Recursive algorithms (or C functions) are those that call themselves.
Recall that each time a recursive call is made, that call gets its own copy of local variables.
Recursive Factorial Algorithm
Pseudocode
Algorithm factorial(n)
Pre:nis a positive integer
Return: returns n!
if (n= 0 ) then
return 1
else
return n*factorial(n-1)
C++
// returns n! assuming n >= 0
int factorial (int n) {
if( n == 0 ) {
return 1;
}
else {
return n * factorial(n-1);
}
}
2

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

2 Designing Recursive Algorithms
2.1 The structure of recursive functions
Thinking recursively: The delegation metaphor
A function call is like delegation. You "hire" a "delegate" to do some work for you.
You give the delegate 3 things:
1. Some data.
2. Some instructions.
3. A place to work.
If you gave your delegate a copy of the same instructions you are using, it’s a recursive function.
Note:
It does not matter at all that your delegate is using the same instructions you are using.
Designing Recursive Algorithms
Recursive Structure
Every recursive function is essentially a conditional.
Factorial
Algorithm factorial(n)
Pre:nis an integer
Return: returns n!
if (n= 0 )
return 1
else
return n*factorial(n-1)
Designing Recursive Algorithms
Base case(s)
At least one branch of the conditional has a very simple return.
Factorial
Algorithm factorial(n)
Pre:nis an integer
Return: returns n!
if (n= 0 )
return 1
else
return n*factorial(n-1)
3