Here are some examples that we may have covered in class:
Factorial:
def fact(n):
if n == 1:
return 1
return n * fact(n-1)
Fibonacci sequence:
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
Number of digits:
def numdigits(n):
if n <= 9:
return 1
return numdigits(n // 10) + 1
Length of a string:
def stringlen(s):
if s == '':
return 0
return stringlen(s[1:]) + 1
Recursion exercises (yes, you MUST write recursive functions below for the problems even though you might be able to write them another way).
1. Create sumdigits(n): given a positive integer n, returns the sum of its digits. Examples: sumdigits(54) ->9, sumdigits(4) -> 4, sumdigits(2000) -> 2
2. Create count_char(s,c): given a string s and a character c, count how many times c occurs in s. Examples: count_char("abcaba","a") -> 3, count_char("fred","c") -> 0. Use the technique shown above in stringlen().
3. Create factors2(n): given a non-negative integer n, returns the number of factors of 2 that it has. Examples: factors2(4) -> 2, factors2(3) -> 0, factors2(24) -> 3
4. Create reverse(s) that reverses the order of the characters in a string. Example: reverse("abc") -> "cba"