Pseudocode: Recursion
Inductive definitions
Many computations are naturally defined
inductively
Base case: directly return the value
Inductive step: compute value in terms
of smaller arguments
Pseudocode: Recursion 2/6
Inductive definitions
Many computations are naturally defined
inductively
Base case: directly return the value
Inductive step: compute value in terms
of smaller arguments
Factorial
n! = n × (n − 1) × · · · × 2 × 1
0! is defined to be 1
factorial(0) = 1
For n > 0, factorial(n) = n *
factorial(n-1)
Pseudocode: Recursion 2/6
Inductive definitions
Many computations are naturally defined
Procedure Factorial(n)
inductively
if (n == 0) {
Base case: directly return the value return(1)
Inductive step: compute value in terms }
of smaller arguments else {
return(n * factorial(n-1))
Factorial
}
n! = n × (n − 1) × · · · × 2 × 1 End Factorial
0! is defined to be 1
factorial(0) = 1
For n > 0, factorial(n) = n *
factorial(n-1)
Pseudocode: Recursion 2/6
Inductive definitions
Many computations are naturally defined
Procedure Factorial(n)
inductively
if (n == 0) {
Base case: directly return the value return(1)
Inductive step: compute value in terms }
of smaller arguments else {
return(n * factorial(n-1))
Factorial
}
n! = n × (n − 1) × · · · × 2 × 1 End Factorial
0! is defined to be 1
factorial(0) = 1 Recursive procedure
For n > 0, factorial(n) = n * factorial(n) is suspended till
factorial(n-1) factorial(n-1) returns a value
Pseudocode: Recursion 2/6
Inductive definitions on lists
Inductive functions on lists
Base case: Empty list
Inductive step: Compute value in terms
first element and rest
Pseudocode: Recursion 3/6
Inductive definitions on lists
Inductive functions on lists
Base case: Empty list
Inductive step: Compute value in terms
first element and rest
Sum of numbers in a list
If l == [], sum is 0
Otherwise, add first(l) to sum of
rest(l)
Pseudocode: Recursion 3/6
Inductive definitions on lists
Inductive functions on lists
Procedure Listsum(l)
Base case: Empty list if (l == []) {
Inductive step: Compute value in terms return(0)
first element and rest }
else {
Sum of numbers in a list
return(first(l) +
If l == [], sum is 0 Listsum(rest(l)))
Otherwise, add first(l) to sum of }
rest(l) End Listsum
Pseudocode: Recursion 3/6
Inductive definitions on lists
Inductive functions on lists
Procedure Listsum2(l)
Base case: Empty list if (l == []) {
Inductive step: Compute value in terms return(0)
first element and rest }
else {
Sum of numbers in a list
return(last(l) +
If l == [], sum is 0 Listsum2(init(l)))
Otherwise, add first(l) to sum of }
rest(l) End Listsum2
Can also add last(l) to sum of
init(l)
Pseudocode: Recursion 3/6
Insertion sort
Build up a sorted prefix
Extend the sorted prefix by inserting the
next element in the correct position
Pseudocode: Recursion 4/6
Insertion sort
Build up a sorted prefix
Extend the sorted prefix by inserting the
next element in the correct position
Procedure InsertionSort(l)
sortedList = []
foreach z in l {
sortedList =
SortedListInsert(sortedlList,z)
}
return(sortedList)
End InsertionSort
Pseudocode: Recursion 4/6
Insertion sort
Procedure SortedListInsert(l,x)
Build up a sorted prefix newList = []
inserted = False
Extend the sorted prefix by inserting the foreach z in l {
next element in the correct position if (not(inserted)) {
if (x < z) {
Procedure InsertionSort(l) newList = newList ++ [x]
inserted = True
sortedList = [] }
foreach z in l { }
sortedList = newList = newList ++ [z]
SortedListInsert(sortedlList,z) }
} if (not(inserted)) {
return(sortedList) newList = newList ++ [x]
}
End InsertionSort
return(newList)
End SortedListInsert
Pseudocode: Recursion 4/6
Insertion sort, inductively
List of length 1 or less is sorted
For longer lists, insert first(l) into
sorted rest(l)
Pseudocode: Recursion 5/6
Insertion sort, inductively
List of length 1 or less is sorted Procedure SortedListInsert(l,x)
newList = []
For longer lists, insert first(l) into inserted = False
sorted rest(l) foreach z in l {
if (not(inserted)) {
Procedure InsertionSort(l) if (x < z) {
newList = newList ++ [x]
if (length(l) <= 1) { inserted = True
return(l) }
} }
else { newList = newList ++ [z]
return( }
SortedListInsert(
InsertionSort(rest(l)), if (not(inserted)) {
first(l) newList = newList ++ [x]
) }
) return(newList)
} End SortedListInsert
End InsertionSort
Pseudocode: Recursion 5/6
Summary
Many functions are naturally defined in an inductive manner
Base case and inductive step
For numeric functions, base case is typically 0 or 1
For lists, base case is typically length 0 or length 1
Use recursive procedures to compute such functions
Base case: value is explicitly calculated and returned
Inductive case: value requires procedure to evaluated on a smaller input
Suspend the current computation till the recursive computation terminates
Warning Without properly defined base cases, recursive procedures will not
terminate!
Pseudocode: Recursion 6/6
