I will use List to teach recursive programming. A recursive function
is a function that calls itself. To avoid infinite loop, there must
be a terminating condition, when to stop the self-call. In our small
exercise, we will concentrate on very small programs. I will "abstract"
the main "method" to be only four. I will use this four methods to
show you how to do recursion. That is, there will be no other "method" in
our program except these four and itself.
I will use the "structure" of data to show how to think recursively,
therefore the "value" in List will be limited to only numbers.
a = [1,2,3,4] is a simple list
b = [[5,6],7] is a complex list
These two kinds of list will be the things that we write recursive program
to manipulate.
First, let us start with defining the four methods:
head(L) return the
first element in the list
tail(L)
return the list without the first element
cons(L1,L2) return the list with L1 as the first
element and the rest is L2
islist(L) return True if L is a list
else return False
a = [1,2,3,4]
print( head(a) )
> 1
print( tail(a) )
> [2,3,4]
b = cons(1, tail(a))
print(b)
> [1,2,3,4]
You can immediately see this invariance:
cons(head(L),tail(L)) == L
Arm with these four simple methods, we will begin our adventure.
Let us count how many element there is in a simple list.
mylen(L)
We use case-analysis. The first case is when the list is
empty. The second case is when the list is not empty.
1) if L is empty the number of element is 0.
We want to make the list smaller step-by-step while we keep counting until
the list is empty.
2) if L is not empty the number of element is 1 + count the tail of
L
so
def mylen(a):
if( a == [] ):
return 0
return 1 + mylen(tail(a))
See when it runs.
mylen([1,2,3])
2) 1 + mylen([2,3])
2) 1 + 1 + mylen([3])
2) 1 + 1 +
1 + mylen([])
2) 1 + 1 + 1 + 0
return 3
We can apply this analysis to another example. We want to print each
element of a list individually. Two cases:
1) the list is empty, stop printing
2) print one element, then do the rest, the list is getting smaller
each step.
def printeach(a):
if( a == [] ):
return
print(head(a))
printeach(tail(a))
printeach([1,2,3])
>
1
2
3
Now, we will tackle a bit more difficult counting task. How to count
a complex list? Let us start with using mylen() with a
complex list.
print(mylen([[5,6],7])
> 2
It counts [5,6] as one element.
We need to check if an element is simple we keep counting as before.
def mylen2(a):
if( a == [] ):
return 0
if( not islist(head(a)) ):
return 1 + mylen2(tail(a))
return ....
We must add another case when the first element is a list. Here is
how a magic happen! If head(a) is a list, surely
we can use our counting method to count it. No need to write any new
method.
def mylen2(a):
if( a == [] ):
return 0
if( not islist(head(a)) ):
return 1 + mylen2(tail(a))
return mylen2(head(a)) + mylen2(tail(a))
Bravo!
Now try,
print(mylen2([[5,6],7]))
> 3
Next task is constructing a new list, using cons().
Write a copy function for a simple list. Two cases:
1) list is empty, return an empty list
2) construct a new list from the first element and the "copy" of the
rest.
In the second case, the input list becomes shorter and shorter until it is
empty.
def copy(a):
if( a == [] ):
return []
return cons( head(a), copy(tail(a)))
a = [1,2,3]
b = copy(a)
print(b)
> [1,2,3]
The cons works by adding the first element to the rest
which will be recursively built.
cons(1, ... cons(2, ...
cons( 3, [] ))) Now a more challenging task, write a function to reverse a list.
rev([1,2,3])
> [3,2,1]
We use a trick of creating an extra variable to hold the new list during
construction.
def rev(a):
return(rev2(a,[]))
Then we can take elements from a, one-by-one, and put that into the second
list using cons(). Definitely, using case-analysis:
1) if the input list is empty, the task is done, return the new list
2) meanwhile, take head() from input, and cons it to the new list
at step 2, the input list becomes shorter and shorter.
def rev2(a,b):
if(a == []):
return b
return rev2(tail(a), cons(head(a),b))
Please take a notice that, the order of putting an element into the new
list is the reverse of the input list. Hence, it reverses the input
list.
Let us tackle another interesting program. Write a program to
substitute one value by another value for all elements in a list.
For example, substitute 1 with 8 in the list [1,2,1,3]
print(subs(1,8,[1,2,1,3]))
> [8,2,8,3]
We use similar trick of "rev" to go into the input list, looking at
element, and construct a new list while the input is getting shorter and
shorter.
def
subs(a,b,c): #
substitute a with b in list c
return subs(a,b,c,[]) # use an extra variable to hold
the new list
when the element is matched, we use the substitute value to construct the
new list, otherwise we use the old value. The recursion occurs when
the input list is getting shorter and shorter. { subs2(...
tail(c) ... ) }
def subs2(a,b,c,d):
if(c == []):
return d
if( head(c) == a ):
return subs2(a,b, tail(c), cons(b,d))
return subs2(a,b, tail(c), cons(head(c),d))
But wait, the output is the reverse of input! (because the new list
is creating in the reverse order, similar to the function "rev"). A
simple solution is to reverse it at the end.
print(subs(1,8,[1,2,1,3]))
> [3,8,2,8]
def subs(a,b,c):
d = subs2(a,b,c,[])
return rev(d)
But that is double the work. So, we will do it in the proper order,
using similar pattern as in copy(). That is, using
cons at the outset (and not using an extra variable to hold the new
list). It means, constructing a new list by
"consing" the first element with while substituting the rest of the input.
The input list is getting shorter and shorter.
def subs3(a,b,c):
if(c == []):
return []
if( head(c) == a ):
return cons( b, subs3(a,b, tail(c)))
return cons( head(c), subs3(a,b, tail(c)))
Before we finish, I want to show how to apply this thinking skill to other
kind of data, for example, array. Yes, you can do recursive in an
array using index for elements in the array too.
A simple example, write a recursive function to sum all elements in an
array. We will use Python list to hold an array.
print(sum([1,2,3]))
> 6
We use index to pick an element and use index to check for terminating
condition. If it is not yet done, self-call until it reaches the end
of array.
We use extra variables for start, end index. The terminating
condition is that the current index reaches the end of array. { i
== end }. The recursive step produces the sum of the current
element with the sum of the rest of the array, hence the "sum2(i+1,end,a)".
"i+1" is the next element and advances the index toward the
end. Remember that the index of an array of size n, is range 0 ..
n-1.
def sum(a):
return sum2(0,len(a)-1,a)
def sum2(i,end,a):
if( i == end ):
return a[i]
return a[i] + sum2(i+1,end,a)
Hope you enjoy the mental gymnastic of this lecture.
Here is my definition of the main four methods. You must include
them into your Python program.
def head(a):
return a[0]
def tail(a):
b = list(a)
c = b.pop(0)
return b
def cons(a,b):
b.insert(0,a)
return b
def islist(a):
return isinstance(a,list)
Of course, all programs must be recursive :-)
1. write a printeach() of a complex list.
2. given a list of list, write a program to produce a list of the
size of each sub-list. lenoflist([[1,2,3],[4,5]])
is [3,2]
3. write a program to produce a new list which each element is
double of the input list. double([1,2,3]) --> [2,4,6]
4. Here is a difficult one, write a program to reverse a complex
list. It means that all sub-list must also be reverse. For
example revx([[1,2],[3,4]]) --> [[4,3],[2,1]]
5. Write a program to sum element-wise of two input lists of the
same size, produce the new list. sumlist([1,2,3],[4,5,6])
--> [5,7,9]
6. Recursion in an array. Do the similar problem as 5. but
using index into the input array instead. Observe how different two
programs (4 and 5) are.
7. In Ajarn Somchai's slide, he asked you to write a program to
"flatten" a complex list. Do it with our four methods. flatten([[1,2],3])
--> [1,2,3]
8. If you really want a mind-bending exercise, write a recursive
program to multiply matrix (not using index), representing a matrix with
list of list.
Solution to the problem 1, 2, 3
last update 29 Mar 2016