owned this note
owned this note
Published
Linked with GitHub
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.
---
Google Drive
Gist
Clipboard
Sign in with Wallet
