Foundations of Algorithms Workshop 3 === ###### tags: `comp10002` `workshop` `c` --- ### FUNctions --- ### Our first function we learnt ```cpp #include <stdio.h> int main(int argc, char **argv) { printf("argc is %d\n", argc); for (int i=0;i<argc;i++) { printf("arg %d is: %s\n", i, argv[i]); } return 0; } ``` --- ### Other functions we have been using ```cpp int scanf(const char *format, ...) int printf(const char *format, ...) ``` --- ### Anatomy of a function ```cpp {return_type} function_name({argument_type} argument_name...) { return {return_type} } ``` ```cpp int add(int a, int b) { int res; res = a + b; return res; } ``` --- ### Further Examples ```cpp int pow(int base, int power) { int result = 1; for (int i = 0; i < power; i++){ result *= base; } return result; } ``` --- ### How to use them? ```cpp= #include <stdio.h> int pow(int base, int power); int main(int argc, char **argv) { int result = pow(1,2); return 0; } int pow(int base, int power) { int result = 1; for (int i = 0; i < power; i++){ result *= base; } return result; } ``` --- ### Prototypes All functions need to be declared before (or above) where they are used. To solve this problem we delcare **prototypes** of the function at the top of the file ```cpp= #include <stdio.h> int function(); int main(int argc, char **argv) { function(); return 0; } int function() { // actual implementation return 5; } ``` --- ### Recursion What happens when a function calls itself? ```cpp int plus(int a, int b){ if (b == 0) { return a; } return 1 + plus(a, b-1); } ``` --- ### Recursion ```cpp plus(0, 3) 1 + plus(0, 2) 1 + 1 + plus(0, 1) 1 + 1 + 1 + plus(0,0) 1 + 1 + 1 + 0 = 3 ``` --- ### Recursion What can we do with it? A lot there are some problems which suit really well to using recursion over using a for or while loop. factorial? ```cpp int factorial(int n) { if (n < 2) { return n; } return n * factorial(n-1); } ``` --- ### Recursion Important things: 1. Recursion, just like loops must always have a certain way to terminate. This is called a base case where we don't call the function anymore. 2. Recursive functions must always work towards the base case - otherwise they will eat up all your ram! --- ### A taste of pointers! --- ### Question 5.1 Write a function max_2_ints that expects two int arguments, and returns the larger of them. Test your function using some suitable scaffolding --- ### Question 5.2 Write a function max_4_ints that expects four int arguments, and returns the largest of them. The obvious way of doing this is somewhat heavy-handed. Can you think abstractly? Is there a role for your previous function, max_2_ints? --- ### Question 5.3 Write an int function int_pow that raises its first argument to the power of its second argument, where the first argument is an int, and the second argument is a positive int. For example, int_pow(3,4) should return the value 81. --- ### Question 5.6 Two numbers are an amicable pair if their factors (excluding themselves) add up to each other. The first such pair is 220, which has the factors [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110], adding up to 284; and 284, which has the factors [1, 2, 4, 71, 142], the sum of which is 220. The next amicable pair is 1,184 and 1,210; and then 2,620 and 2,924. Write a function that takes two int arguments and returns true if they are an amicable pair. Then, test your function by writing a main program that reads an integer n and searches from n for the first amicable pair where n is one of the partners. --- ### Question 5.13 You probably wrote an iterative function for Exercise 5.3. Now write a recursive one for the same task. ---