CMPT120 J.

Ye

Recursion

• Recursive Definition
• Recursive Programming
• Examples and Exercises
Recursive Definition

• Recursion is a fundamental programming technique that can

provide an elegant solution for certain kinds of problems

• Before applying recursion to programming, let’s examine

recursive definition

• A recursive definition is a definition in which the concept

being defined is used in the definition itself

2
Recursive Definition (cont)
• Consider a list of numbers, e.g.

24, 88, 40, 37

• Such a list can be defined as follows:

A LIST is a number
or a number comma LIST

• That is, a LIST is defined to be a single number, or a number

followed by a comma followed by a LIST

• The concept of a LIST is used to define itself – recursive definition

3
Recursive Definition (cont)
• The recursive part of the LIST definition is used several
times, terminating with the non-recursive part:
number comma LIST
24 , 88, 40, 37

number comma LIST

88 , 40, 37

number comma LIST

40 , 37

number
37

4
 Recursive Definition
Infinite Recursion
• All recursive definitions have to have a non-recursive part
• If they didn't, there would be no way to terminate the
recursive path
• Such a definition would cause infinite recursion
• This problem is similar to an infinite loop, but the non-
terminating "loop" is part of the definition itself
• The non-recursive part is often called the base case

5
Recursive Definition (cont)
• N! , for any positive integer N, is defined to be the
product of all integers between 1 and N inclusive
• The above definition can be expressed recursively as:
1! = 1
N! = N * (N-1)!
• A factorial is defined in terms of another factorial
• Eventually, the base case of 1! is reached
• This definition also gives a (recursive) way of calculating it

6
Recursive Definition (cont)

5!
120
5 * 4! 24

4 * 3! 6

3 * 2! 2
2 * 1!
1

7
Recursive Programming
• A recursive solution has to be in a function!
• A recursive function – a function that invokes itself (with a
“smaller” argument)
• The code of a recursive function must be structured to
handle both the base case and the recursive case
• Each call to the function sets up a new execution
environment (stack), with new parameters and local
variables
• As with any function call, when the function completes,
control returns to the function that invoked it (which may be
an earlier invocation of itself)
• Examples and Exercises … 8
Recursive Programming (cont)
• How to implement the recursive factorial function?

def factorial(n):
if n == 1:
result = 1
else:
result = n * factorial(n-1)
return result

• How to implement the factorial function iteratively (using

loop)?

9
Recursive Programming (cont)
result = 6
main
factorial(3)

result = 2
factorial

factorial(2)

result = 1
factorial
factorial(1)

factorial

10
Thinking Recursively

When designing recursive solution:

• Ignore details
– forget how stack works
– forget the suspended computations
– yes, this is an "abstraction" principle!
– and encapsulation principle!

• Programmer just think “big picture”

– Let computer do "bookkeeping"

11
Thinking Recursively: power
• Consider function power(x,n) (n is integer, n >= 0)
n
• To calculate xn :
x * x * x * … * x * x
A smaller subtask is xn-1

n-1
• suppose xn-1 is computed, how to compute xn?
– In other words, how to go from the smaller subtask to the original
one?
– Easy! xn-1 * x
• And ensure base case will be met
• Now how to define the recursive power function? 12
Recursive Design Techniques

• Don’t trace entire recursive sequence!

• Just check 3 properties:
1. no infinite recursion
• at least one base case
• the size of the argument is smaller in the recursive
call

2. stopping/base case(s) return correct value(s)

3. recursive case(s) return correct value(s)

13
Recursion Versus Iteration
• Recursion not always "necessary“
• Any task accomplished with recursion can also be
done without it
– non-recursive, also called iterative -- using loops

• Recursive:
– Runs slower, uses more storage
– Elegant solution; less coding

• Now we will do some recursive function analysis, as well as

recursive coding.
14