---
tags : Programming Course (C/C++)
---

# Computer Programming(2)

[TOC]

## 考古題參考ans

(https://hackmd.io/@CSnoob/tmpcode)

## Recursion

### What is recursion?

> Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

### Ex1: adding from 0 to n

:::info
if n is 3
calling subfunction in main: return 3+add(2)
calling add(2): return 2+add(1)
calling add(1): return 1+add(0)
calling add(0): return 0

add(3)
= 3+add(2)
= 3+2+add(1)
= 3+2+1+add(0)
= 3+2+1+0
:::

#include <iostream>
using namespace std;
int add(int k){
    if(k>0){
        return k+add(k-1);
    }else{
        return 0;
    }
}
int main(){
    int n;
    cin>>n;
    cout<<add(n);
    return 0;
}

### Ex2: factorial function

:::info
calculate n!=?
if n is 3
factorial(3)
= 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1
:::

#include <iostream>
using namespace std;
int factorial(int k){
    if(k>1){
        return k*factorial(k-1);
    }else{
        return 1;
    }
}
int main(){
    int n;
    cin>>n;
    cout<<factorial(n);
    return 0;
}

### Ex3: k to the power of n

::: info
if k is 3, n is 5
p_fuction(3,5)
= 3 * p_fuction(3,4)
= 3 * 3 * p_fuction(3,3)
= 3 * 3 * 3 * p_fuction(3,2)
= 3 * 3 * 3 * 3 * p_fuction(3,1)
= 3 * 3 * 3 * 3 * 3
:::

#include <iostream>
using namespace std;
int p_function(int i, int j){
    if(j>1){
        return i*p_fuction(i,j-1);
    }else{
        return i;
    }
}
int main(){
    int k, n;
    cin>>k>>n;
    cout<<p_function(k,n);
    return 0;
}

### Ex4: fibonacci

:::info
$$F_n=
\begin{cases}
1& \text{x=1,2}\\
F_{n-1}+F_{n-2}& \text{x>2}
\end{cases}$$

if n is 5
fib(5)
= fib(4)+fib(3)
= [fib(3)+fib(2)] + [fib(2)+fib(1)]
= fib(2)+fib(1)+1+1+1
= 1+1+1+1+1
= 5
:::

#include <iostream>
using namespace std;
int fib(int k){
    if(k<3){
        return 1;
    }else{
        return (fib(k-1)+fib(k-2));
    }
}
int main(){
    int n;
    cin>>n;
    cout<<fib(n);
    return 0;
}

### Ex5: greatest common divisor

:::info
gcd of i and j
if i is 9 and j is 24

\begin{align*}
(9÷24=0\cdot\cdot\cdot\cdot9)\\
24÷9=2\cdot\cdot\cdot\cdot6\\
9÷6=1\cdot\cdot\cdot\cdot3\\
6÷3=2\cdot\cdot\cdot\cdot0\\
3÷0=無意義
\end{align*}
gcd is 3
:::

#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(b==0){
        return a;
    }else{
        return gcd(b,a%b);
    }
}
int main(){
    int i, j;
    cin>>i>>j;
    cout<<gcd(i, j);
    return 0;
}

## Array

### How to pass array to sub function?

//傳遞array in C -> pass by address
#include <iostream>
using namespace std;
void show(int arr[]){
    for(int i=0; i<5; i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
int main(){
    int a[5]={0, 1, 2, 3, 4};
    show(a);
    return 0;
}

#include <iostream>
using namespace std;
const int row=3, col=4;
void search(int arr[][col], int ans[]){
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(arr[i][j]<ans[0]){
                ans[0]=arr[i][j];
            }
            if(arr[i][j]>ans[1]){
                ans[1]=arr[i][j];
            }
        }
    }
    return;
}
int main(){
    //cin>>row>>col;
    int a[row][col]={0};
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>a[i][j];
        }
    }
    int b[2]={a[0][0], a[0][0]};
    search(a,b);
    cout<<b[0]<<" "<<b[1];

    return 0;
}

## Pointer

### What is pointer?

### How to use pointer?

### How to pass pointer to sub function?

### What is the relationship between pointer and array?

## Parameter Passing

### What is pass by value?

### What is pass by address?

### What is pass by reference?