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

...