1 Recursive functions

Try the following two function definitions. Note: you need a blank line at the end of a function definition.

Calculating the sign (-1,1 or 0) of a number: 

def sign_function(x): 
  if x < 0: 
    return -1 
  elif x == 0: 
    return 0 
  else: 
    return 1 
   
print sign_function(8)
The sign function is a function, but not a recursive function. The following function is recursive because it calls itself. This means that the name of the function shows up in a return statement.

Calculating factorials: 

def fact(n): 
  if n == 0 or n == 1: 
    return 1 
  else: 
    return (n * fact(n-1)) 
 
print fact(7)

1.1 Exercises

1) Write a recursive function fibo(x) that calculates the Fibonacci numbers. The conditions should be:
  • fibo(1) returns 0
  • fibo(2) returns 1
  • fibo(x) for x < 1 returns a message saying that x must be > 0
  • fibo(x) for x > 2 contains a recursive call to fibo(x-1) and fibo(x-2)

    2) Write a recursive function that determines whether a word is a palindrome (i.e. it reads the same in either direction, such as radar, civic, rotator). Hints:

  • write conditions for words of length 0 and 1
  • len(word) returns the length of word
  • word[0] shows the first character;
  • word[len(word)-1] shows the last character
  • word = word[1:len(word)-1] removes the first and last character.

    3) Calculate the greatest common divisor of two integers using the Euclidean algorithm:

  • using numbers m and n;
  • if n = m, you are finished;
  • otherwise, sort them so that m < n;
  • if m = 0, return n;
  • otherwise, return the greatest common divisor of (m, n % m).

    For example: find the greatest common divisor of 26 and 14.
    m = 14; n = 26
    26 % 14 = 12
    find the greatest common divisor of (14, 12)
    m = 12; n = 14
    14 % 12 = 2
    find the greatest common divisor of (12, 2)
    m = 2; n = 12
    12 % 2 = 0
    find the greatest common divisor of (2, 0)
    m = 0; n = 2
    return 2

    4) Optional exercise: write a recursive function that checks whether an expression contains matching, nested brackets. For example, the expression "(c(()b))" is ok, whereas ")n()" is not. The brackets must be nested one inside the other, thus, "()()" is not ok.

    2 Properties of functions

    Many mathematical properties and points of functions can be read from the graph of a function:

    properties/pointsgraph
    domainx-values for which the function is defined
    range/image (a subset of the co-domain) y-values which the function actually takes
    symmetricmirrored along y-axis
    continuouscan be drawn in one line without stopping
    bijective/strictly monotonous graph is strictly increasing or strictly decreasing
    boundedvalues don't approach infinity
    root/zeropoint where the graph intersects with x-axis
    local maximum or minimumpoint where graph changes between rising/falling
    global maximum or minimumhighest/lowest point of the graph
    inflection pointgraph changes its concavity

    Use Wolfram Alpha to check the properties of the following functions based on their graphs:

    You can also use an on-line version of sage for this exercise, but it is more complicated. I have created a worksheet which shows the solution to this exercise using sage.