Scribd
Upload
14 views7 pages

COMP6100 - Week 2 Discussions

The document discusses recursive functions and how to determine if a number is prime or not. It provides examples of recursive functions to calculate factorial, greatest common divisor, division and modulus. It also provides exercises to write recursive functions to check primality, print prime numbers between two numbers, calculate division and modulus recursively, and sum the digits of a number recursively.

Uploaded by

Theresa Stewart
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views7 pages

COMP6100 - Week 2 Discussions

The document discusses recursive functions and how to determine if a number is prime or not. It provides examples of recursive functions to calculate factorial, greatest common divisor, division and modulus. It also provides exercises to write recursive functions to check primality, print prime numbers between two numbers, calculate division and modulus recursively, and sum the digits of a number recursively.

Uploaded by

Theresa Stewart
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Self-Assessment – Functions

1. Describe the differences between Iteration and Recursion.

Both iteration and recursion are techniques used to repeat a set of instruction, but they work in

different ways. Iteration uses a recursive function call or loop like ‘for’ or ‘while’ to repeatedly

execute a block of code until a specific condition is met. For example, if you have a stack of

dishes to be washed, in iteration, you start with the first item in the loop, the dish, and you wash

it, then you repeat those two steps until the stack of dishes is done so the loop condition is met.

With recursion, the function calls itself with smaller and simpler versions of the original problem

until a base case is reached, at which point the solution is built back up by returning values from

each function call. For example, with the same stack of dishes, in a recursion function, you

would take a dish from the top of the stack, you say to yourself, I am going to wash this dish, and

you wash it. You look back at the stack, you think, the stack is smaller with one less dish. You

take another dish and repeat the until you have emptied the stack and stop going back to the

stack.

2. Write a function in python which will help a group of friends out for dinner determine
their portion of the bill. The function should take the bill amount and number of friends
and return each person’s contribution and a tip amount. The tip amount is 10% of the bill
amount.
3. Write a recursive function in python which calculates the greatest common divisor of two
integers i.e. the largest integer that divides both a and b with no remainder. For example,
the GCD of 16 and 28 is 4. The method for computing GCD is the Euclid’s algorithm. It
is based on the observation that, if r is the remainder when a is divided by b, then the
common divisor of a and b are precisely the same as common divisors of b and r. Thus,
we can use the equation: gcd(a,b)= gcd(b,r) For example, gcd(206,40) = gcd(40,6) =
gcd(6,4) = gcd(4,2) = gcd(2,0) = 2 where 2 is the gcd of 206 and 40.
4. Complete the following, recursive function (helper) to calculate the factorial of a given
number. helper maintains the state of the computation. The factorial of a number N, is
calculated as follows:
N! = 1 x 2 x 3 x... x N

Below are factorial values for a few small integers,


N Result
1 1
2 2
3 6
4 24

def ifactorial(n):
def helper(x, result):
if … :
return …
else:
return …

return helper …
Learning Activity 1.5

Functions
1. An integer greater than 1 is said to be prime if it divisible by only 1 and itself. For example,
2,3,5,7 are prime numbers, but 4, 6, 8 and 9 are not. Write a function isPrime that determines
whether a number is prime or not. The function takes a parameter n and checks if there exists
a number from 2 to n that n is divisible by [Hint: you can use for loops]. If n is divisible by
such a number, then it is not a prime number and false must be returned. Return true if the
number is a prime number. Remember that 1 is not a prime number. e.g. isPrime(5) --‐-> True

2. Use isPrime function in a function primes that take two numbers as parameters and prints all
the prime numbers between those two numbers (e.g. 2 and 10). Ensure that isPrime is local
function and can only be accessed by function primes. e.g. primes(2,10) --‐-> 2,3,5,7
isPrime(3) --‐-> syntax error
Activity 1.6

Functions
1. Write recursive functions in python that calculate div and mod. div takes two integers as input
and keeps on subtracting the second from the first until the first number becomes less than the
second number. The function keeps a track of how many times the second number is subtracted
from the first and returns that number as the answer.
mod also takes two integers as input and keeps on subtracting the second from the first until the
first number becomes less than the second number. When the first number becomes less than the
second, the value of the first number is the answer.

2. Two functions lastDigit and allButLast are given below. Given a number n as an argument the
function lastDigit returns the last digit of that number and allButLast returns the number with its
last digit taken off. Write a recursive function sumDigits which sums all digits in a given
number. For example, 234 will be 2+3+4, hence 9 will be returned.
def lastDigit(n):
return mod(x,10)
def allButLast(n):
return div(x,10)
To write sumDigits, one solution is to extract the last digit from the given number n, then call the
function with an argument from which the last digit has been removed.

You might also like