CSC231 Recursive Multiplication
--D. Thiebaut 15:10, 29 November 2010 (UTC)
Definition
- a and b are integers
- a is a positive integer and can be null
- algorithm
- mult( a, b ) returns a multiplied by b
- if a==0 mult( a, b ) = 0
- if a==1 mult( a, b ) = b
- otherwise mult( a, b ) = mult( a-1, b ) + b
Python Version
#! /usr/bin/python
# mult.py
# implements multiplication as a recursive
# process. Works only with integers. a must
# be positive.
# mult( a, b ) = 0 if a == 0
# mult( a, b ) = b if a == 1
# = b + mult( a-1, b ) otherwise
#
def mult( a, b ):
if a==0: return 0
if a==1: return b
return b + mult( a-1, b )
def main():
a = 0
b = 100
print "a = %d b = %d mult( %d, %d ) = %d " \
% ( a, b, a, b, mult( a, b ) )
a = 1
b = 100
print "a = %d b = %d mult( %d, %d ) = %d " \
% ( a, b, a, b, mult( a, b ) )
a = 3
b = 100
print "a = %d b = %d mult( %d, %d ) = %d " \
% ( a, b, a, b, mult( a, b ) )
a = 100
b = 0
print "a = %d b = %d mult( %d, %d ) = %d " \
% ( a, b, a, b, mult( a, b ) )
main()
Assembly Version