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

14 pages24 viewsWinter 2016

Department

Computer ScienceCourse Code

CMPT 115Professor

Jason BowieLecture

11This

**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 Caveats about Recursion 13

4.1 When should recursion be used in C++? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Time Complexity of Recursive Algorithms 14

1 Recursive Deﬁnitions

Dispelling concerns about recursion

•Recursion is a form of repetition based on function calls, instead of loops.

•You may like loops better because you practice those more.

1

###### You're Reading a Preview

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·(n−1)! if n > 0(inductive step)

•Suppose we re-formulate the !operation as a function:

factorial(n) = (1if n= 0

n·factorial(n−1) 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

###### You're Reading a Preview

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.

•You wait until your delegate returns to you with the answer you asked for.

•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

###### You're Reading a Preview

Unlock to view full version

#### Loved by over 2.2 million students

Over 90% improved by at least one letter grade.