Homework 1: Basic Recursion Give all definitions as recursive (or indirectly recursive) C++ functions. No loops!(for , while, etc.) Some questions are substantially similar to others, so that if you get help on one problem, you can try similar problems on your own.

1. Define function sum(n)which returns the sum of the first n positive integers, 1+2+3+ . . . +n.

2. Define function sum_squares(n)which returns the sum of the first n squares, 12 +2 2 +3 2 + . . . +n 2.

3. Define function sum_cubes(n)which returns the sum of the first n cubes, 13 +2 3 +3 3 + . . . +n 3. 4. Define function print_threes(n)which prints the digit 3 to the console n times. 5. Define function print_quacks(n)which prints "Quack!" to the console n times. 6. Define function print_sequence(m,n)which prints the sequence of integers from m ton, inclusive. If mn the function prints (decreasing) m, (m1), (m2), . . . , (n+1),n. (You can omit the commas.) 7. Define function num_threes_in_range(m,n)which returns the total number of 3 s appearing in the digits of the integers m to n, inclusive. For example, num_threes_in_range(20,35)returns 8 because the numbers in the range with 3 s (23, 30, 31, 32, 33, 34, 35) have a total of eight 3s. You may use helper functions. 8. The Fibonacci sequence can be extended to the negative integers by solving its defining recurrence fn =f n1 +f n2 for fn2 : fn2 =f n f n1 . So if f0 =0 and f 1 =1, then f 1 =1,f 2 = 1,f 3 =2, etc. Define function fib(n) which returns the n-th Fibonacci number for any integer n, whether positive, negative, or zero. 9. The sequence x0 =1,x 1 =2,x 2 =3, and for n> 2, xn =x 1 +x 2 +x 3 is computed by the following C++ function.

unsigned long int x(unsigned long int n) { if (n == 0) return 1; else if (n == 1) return 2; else if (n == 2) return 3; else return x(n-1) + x(n-2) + x(n-3); } Alas, it takes forever to compute x50 using this function. Redefine this function using a recursive helper function, x_helper,so computing x50 takes milliseconds, not minutes or hours. 10. Using a tail recursive helper function, define the factorial function, factorial(n), which returns n!, the product of the first n positive integers. Note: 0! equals 1.