# #C Programming (II)-4
## Recursive, Random
English: Lei KuoLiang
nicolaslouis@mail.fcu.edu.tw
Chinese(TW): Wang M.H
---
### Final topic grouping
Please complete the grouping before 11AM!
! [] (https://i.imgur.com/X2S6aSf.png)
https://forms.gle/kBa4HNpRBziFBqyi8
---
### Course Catalog of the Week
0. Review
1. Recursive
* Factorial
* Tossing and Dividing
* fibonacci sequence (practice)
2. Random
---
## Lesson review last week
----
### Function
----
#### Call by value
If the parameter is a numeric value (int, float, double, char ...), when performing a function operation, ++ will not affect the value of the original variable
```c
int add(int a, int b) {
a += b;//Does not affect val1 in main
return a;
}
int main() {
int val1 = 5, val2 = 6, val3;
val3 = add(val1, val2);
printf("val1 = %d\n", val1);
printf("val3 = %d\n", val3);
}
```
Operation result
```
val1 = 5
val3 = 11
```
----
#### Call by reference
If the parameter is an array, ++ will affect the value of the original variable when performing a function operation
```c
void zeroing(int a[], int n) {
for(int i = 0; i < n; i++)
a[i] = 0;
}
int main() {
int arr[5] = {1, 2, 3, 4, 5};
zeroing(arr, 5);
for(int i = 0; i < 5; i++)
printf("%d ", arr[i]);
}
```
Operation result
```
0 0 0 0 0
```
----
If the function has a return value (type is not void), add "` return value; `" at the end of the function or where you want to end it
```c
int isPrime(int num){
if (num == 1)
return 0; //End function, return 0
else
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return 0; //End function, return 0
}
return 1; //End function, return 1
}
```
----
If the function has no return value (type void), add "` return; `" at the end of the function or where you want to end, or automatically return the braces at the end of the function
```c
//Continue the code on the previous page
void printPrime(int max) {
if (max < 2)
return; //End function
for (int i = 2; i <= max; i++) {
if(isPrime(i))
printf("%d\n", i);
}
} //End function
```
----
### math.h
Libraries for Mathematical Functions
`#Include <math.h>` before use
----
#### Trigonometric functions
|||
| -------- | -------- |
| double sin (double); | sine |
| double cos (double); | cosine |
| double tan (double); | tangent |
----
* Constant π: M_PI = 3.14159265358979323846
* `#Define _USE_MATH_DEFINES` is required before` #include <math.h> `
(Dev-C ++ and VS will spray wrong without define)
* E.g:
```c=
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
int main(){
printf("%lf", sin(M_PI / 2));
}
```
----
#### Exponential logarithm
|||
| -------- | -------- |
double sqrt (double);
double log (double); natural logarithm (log (n) = ln n = log ~ e ~ n)
double log10 (double); log base 10 (log10 (n) = log ~ 10 ~ n)
double pow (double x, double y); calculate the power of y with base x (pow (x, y) = x ^ y ^)
----
#### Take integer, absolute value
|||
| -------- | -------- |
double ceil (double); | round up (unconditional entry)
double floor (double); |
double round (double); | Rounding (after version C99)
int abs (int); | find the absolute value of an integer
double fabs (double);
---
There are two ways to run a function repeatedly:
1. Iteration (it's a circle! You'll be there long ago)
2. Recursive (to be taught today)
----
Give an example of ** iteration ** (loop)
```c=
int factorial(int n){ //factorial
int result = 1;
for(int i = n; i; i--)
result *= i;
return result;
}
```
----
An example of ** recursive **
```c=
int factorial(int n){ //factorial
if(n <= 1)
return 1;
return n * factorial(n - 1);
}
```
---
## Recursive
### (n. recursion / adj. recursive)
A function that will call itself
----
### Key concepts of recursion
1. How to accomplish your goal by calling yourself in a function
2. How to pass parameters
3. Stopping point for recursion
The next example will slowly parse how to design recursion
---
### factorial
$n! = n \times (n - 1) \times (n - 2) \times ... \times 2 \times 1$
----
Known when $ n> 1 $:
$ n! = n \ times (n-1) \ times (n-2) \ times ... \ times 2 \ times 1 $
then:
$ n! = n \ times (n-1)! $
----
Learn：
$$
n! =
\begin{cases}
1, & \text{if $n=0\ or\ 1$} \\
n \times (n-1)!, & \text{if $n>1$}
\end{cases}
$$
Written in C：
```c=
int factorial(int n){ //factorial
if(n <= 1)
return 1;
return n * factorial(n - 1);
}
```
----
Note: there must be a stopping point for recursive functions
----
Next, let's see how this function works
Take calling `factorial (4)` as an example
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
---
### Toss and divide
----
<!-- .slide: data-transition="none" -->
First write 343 and 91
----
<!-- .slide: data-transition="none" -->
343 % 91 = 70
----
<!-- .slide: data-transition="none" -->
91 % 70 = 21
----
<!-- .slide: data-transition="none" -->
70 % 21 = 7
----
<!-- .slide: data-transition="none" -->
21 % 7 = 0
----
<!-- .slide: data-transition="none" -->
Has anything been observed?
----
<!-- .slide: data-transition="none" -->
Value passing
----
<!-- .slide: data-transition="none" -->
Written as recursion:
```c=
int gcd(int n,int m)
{
if(!(n % m))
return n;
return gcd(m, n % m);
}
```
----
<!-- .slide: data-transition="none" -->
----
<!-- .slide: data-transition="none" -->
---
### Exercise one
Known fibonacci sequence
$$
a_n =
\begin{cases}
n, & \text{if $n=0\ or\ 1$} \\
a_{n-1}+a_{n-2}, & \text{if $n>1$}
\end{cases}
$$
Try to find the nth term of the fibonacci sequence using recursion
----
* There will be multiple lines of input, each line has an integer n,
0 ≦ n ≦ 30.
* Print out the values of a ~ n ~.
```
Input：
0
3
10
30
Output：
0
2
55
832040
```
---
## Random (pseudo-random)
`rand ()` function defined by `stdlib.h`
pseudo phonetic: / ˈsudo /
----
`int rand()`Will return an integer value between 0 and 32767
```c=
#include <stdio.h>
#include <stdlib.h>
int main(){
for(int i = 0; i < 10; i++)
printf("%d\n", rand());
}
```
----
However, you will find that the results after running many times are the same ~
That's because the program uses the same random number table!
At this time we need to initialize the random number table !!
----
Use `void srand (int seed)` defined by `stdlib.h` to initialize random number table
And the parameter `seed` is a parameter in the" Pseudo Random Number Generation Algorithm "
In short, `seed` will determine how the random number table looks.
----
We usually use the current time as `seed`
In order to get the current time, we need to use the `int time (int * timer)` function defined by `time.h`
`time (NULL)` can get the number of seconds between 1970/1/1 00:00 UTC and the current time
----
The following can randomly get 10 integer values between 0 and 32767.
```c=
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
srand(time(NULL));
for(int i = 0; i < 10; i++)
printf("%d\n", rand());
}
```
----
### Random range
Because `rand ()` only returns integer values between 0 and 32767.
If you want to customize a random range, use arithmetic controls
* 0 ~ 9 random integer: `rand ()% 10`
* 1 ~ 6 random integer: `rand ()% 6 + 1`
* -10 ~ 10 random integer: `rand ()% 21-10`
* And so on
---
### Exercise 2
Implement "Ultimate Password" mini game:
* First, randomly generate an integer n, 1 ≦ n ≦ 100
* Next, let the user enter the integer repeatedly.
* If the input is other than 1 ~ 100, "OUT OF RANGE" is printed
* If the input is less than n, "TOO SMALL" is printed
* If the input is greater than n, "TOO BIG" is printed
* If the input is equal to n, then "YOU WIN" is printed.
And end the program
----
---
### Homework
----
Implement "1A2B" Guess the Number game:
`` `
* At the beginning of each game, randomly generate a set of four numbers arranged from left to right, such as 0567.
(The number 0 can be at the front, and the number cannot be repeated)
* Next, print ">>", and then let the user enter the four numbers repeatedly. After entering:
-If the input format is wrong (entering repeated numbers or not 4 numbers), then print "INPUT ERROR"
-If it does not match the correct answer, print a prompt with the prompt format nAmB:
* nA means that n numbers appear in the correct answer and appear in the correct position,
* mB means that m numbers appear in the correct answer, but appear in the wrong place.
* Example: If the answer is 0567, the result of entering 6597 is 2A1B, where:
2A means that 2 numbers appear in the correct answer and appear in the correct position,
1B means 1 digit appears in the correct answer, but appears in the wrong place.
-If it matches the correct answer, print "YOU WIN" and ask if you are playing once.
```
----
(https://i.imgur.com/pRfwTp5.png)
---
### Research: Recursive Classic Topic-"Hanoi Tower"
* There are three poles A, B, C. There are N (N> 1) perforated discs on the A pole, and the disc size decreases from bottom to top. Requires that all discs be moved to the C-rod as follows:
1. Only one disc can be moved at a time;
2. Large plates cannot be stacked on small plates.
* Tip: The disc can be temporarily placed on the B pole, or the disc removed from the A pole can be moved back to the A pole, but both rules must be followed.
* Q: How to move? How many times must I move? --Wikipedia
----
The solution logic of this problem is actually recursion.
And there are many related answers on the Internet ~
If you can figure out the logic of this question,
It will definitely be of great help to future programming capabilities ~
---
### Feedback Questionnaire
https://forms.gle/Mq1LwHgowCRxbcDq8
---
All courses have been taught ~~
---
But next week (12/9) roll call ~
Then also roll call on 12/23 ~~
---
Next week will teach a little HackMD (the final report will be used)
---
Then take the test next week (12/16)
---
###### tags: `1082 Ai-Mod-Eng-LKL`
{"metaMigratedAt":"2023-06-15T02:09:22.261Z","metaMigratedFrom":"YAML","title":"W4- Recursive, Random","breaks":true,"slideOptions":"{\"transition\":\"slide\"}","contributors":"[{\"id\":\"befaa4d9-75b6-4c05-baa7-7949e0ffa1e2\",\"add\":13512,\"del\":2114}]"}