Recursion Examples (Python)

Recursion I believe is best understood by first practicing with small scale examples. Attempt to provide a solution for the following problems before checking the answers provided (Doing otherwise will not help you gain experience on this topic and will defeat the purpose of this post).

1. Write this function recursively:

# sum_even(n): number -> number
# sum_even(n) is the sum of even numbers from 0 to N.
def sum_even(n):
 total = 0
 for i in range(2, n+1,2):
   total = total + i
 return total

2. Write this function recursively:

# sum_odd(n): number -> number
# sum_odd(n) is the sum of odd numbers from 1 to N
def sum_odd(n):
 total = 1
 for i in range(1,n+1,2):
   total = total + i
 return total

3. Write this function recursively:

# prod(L): number -> number
# prod(L) is the product of numbers in list L
# should return 1 if list is empty
def prod(L):
  product, i = 1,0
  while i < len(L):
    product = product * L[i]
    i = i + 1
  return product

4. Write a recursive function to compute the sum of numbers from 1 to n.

**Assume that n is always positive**

5. Write a recursive function that computes and returns the sum of all elements in a list where the list and its size are given as parameters e.g def elementSum(L,n) where n == len(L)

**Assume that elementSum(L,n) does not receive an empty list**

6. Write a recursive function to compute the maximum element in a list. Its only parameter should be the list. e.g maxElement(L)

**Assume that maxElement(L) does not receive an empty list**

7. Write a recursive function to compute the minimum element in a list given the list and the number of elements in the list e.g minElement(L,n) where n == len(L)

**Assume that minElement(L,n) does not receive an empty list**

8. A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction. Composing literature in palindromes is an example of constrained writing. Wikipedia

Write a recursive function that determines whether a string is a palindrome. Your function should receive the string as its only parameter. e.g isPalindrome(S)

**Assume that your string does not contain punctuations and that all the characters are lower case letters**

Answers
Solution to Question 1

def sum_even(n):
  if n < 1:
    return 0
  elif n%2 != 0:
    return sum_even(n-1)
  else:
    return n + sum_even(n-2)

Note that this function returns 0 for all non positive values of n just as is defined in the original function

Solution to Question 2

def sum_odd(n):
  if n < 2:
    return 1
  elif n%2 == 0:
    return sum_odd(n-1)
  else:
    return n + sum_odd(n-2)

Note that this function returns 1 if n is not greater 0 as is defined in the original function

Solution to Question 3

def prod(L):
  if L == []:
    return 1
  elif len(L) == 1:
    return L[0]
  else:
    return L[0] * prod(L[1:])

Note that this function returns 1 if the list is empty as is defined in the original function

Solution to Question 4

def oneToN(n):
  if n == 1:
    return 1
  else:
    return n + oneToN(n-1)

Solution to Question 5

def elementSum(L,n)
  if n == 1:
    return L[0]
  else:
    return L[0] + elementSum(L[1:],n-1)

Solution to Question 6

def maxElement(L):
  if len(L) == 1:
    return L[0]
  else:
    max = maxElement(L[1:])
    if L[0] > max:
      return L[0]
    else
      return max

Solution to Question 7

def minElement(L,n):
  if n == 1:
    return L[0]
  else:
    min = minElement(L[1:],n-1)
    if L[0] < min:
      return L[0]
    else
      return min

Solution to Question 8

def isPalindrome(S):
  # Remove spaces in the string
  N = S.split()
  N = ''.join(N)
  if len(N) == 1 or len(N) == 0:
    return True
  else:
    if N[0] == N[-1] and isPalindrome(N[1:-1]):
      return True
    else:
      return False

Note that the spaces were removed as you only need to compare the individual characters.

**If you have any questions or think that I have made a mistake, please leave a comment**

Advertisements

5 thoughts on “Recursion Examples (Python)

  1. On your palindrome problem, it says a palindrome like:

    “Able was I ere I saw Elba.”

    is false. I’m not sure if you’re just trying to keep things simple, but if you add the following two lines:

    s = s.strip(” !@#$%^&*()-_+={}[]|\\:;’?,./\””)
    s = s.lower()

    your code will catch these types of palindromes as well.

    (Note) in lieu of:

    s = s.strip(” !@#$%^&*()-_+={}[]|\\:;’?,./\””)

    you could alternatively:

    import string # outside the function
    spec = string.punctuation + string.digits + ” ”
    s = s.strip(spec)

    Thanks for putting up this list, It’s really helping me to practice recursion.

    1. For more complex scenarios you are right, however, I did state an assumption below the question. In any case, I’m glad to know that this has helped you.

  2. The answer to the sixth program is wrong, since it is expected that such program as was written in the ask will return the highest variable in the list, but it doesn’t do so. It only return True when it reaches to that maximum variable.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s