aaa6.qmd

---
title: "R: Introduction"
format:
    html:
      toc: true
      self-contained: true
editor_options: 
  chunk_output_type: console
---

## Installing R

Go to the The Comprehensive R Archive Network (CRAN): https://cran.r-project.org/

![Rcran](C:/Users/akl0407/Desktop/Courses/2023/Fall 2023/STAT350 Fall 2023/STAT350-class-notes/images/Rcran.jpg)

Under "Download and Install R," choose "Linux," "MacOS X" or "Windows." If you choose Windows, on the next page choose "base," and on the following page choose "Download R 4.3.1 for Windows" to download the setup program.

If you choose MacOS X or Linux you will need to read through the instructions to find the downloads you need for your machine.

Once you have downloaded the setup program, execute it and follow the instructions for installing R on your system. If you have an earlier version of R already installed, you may continue to use it, or you can uninstall it and then install the most recent version, which is R 4.3.1.

## Installing RStudio

https://rstudio.com/products/rstudio/download/

Choose your version: RStudio Desktop, Open Source License, Free. After you install RStudio, you can double click on it and open:

**1. Base case:** This is the simplest case that can be answered directly, and the function does not call itself.

**2. Recursive case:** This is a relatively more complex case that cannot be answered directly, but can be described as a smaller instance of the same problem. In this case, the function calls itself to answer the smaller problem.

Below is an example, where we defined a function that computes the factorial of an integer by recursion.

```{r}
factorial<-function(n)
{
  if(n==1)      #Base case
  {
      return(1)  
  }        
  return(n*factorial(n-1)) #Recursive case
}
factorial(5)
```

In the above example, the case $n=1$ is the base case, where the function does not need to call itself, and returns 1. All other cases, where $n>1$, and $n \in \mathbb{Z}$ are recursive cases, where the function calls itself with a smaller instance of the same problem.

A recursive function must satisfy the following conditions:

1.  There must be a case for all valid inputs.

2.  There must be a base case that makes no recursive calls.

3.  When the function makes a recursive call, it should be to a simpler instance and make forward progress towards the base case.

**Example:** Write a recursive function that returns the $n^{th}$ term of the Fibonacci sequence, where $n$ is an integer, and $n>0$. In a Fibonacci sequence, each number is the sum of the preceding two numbers, and the sequence starts from $0,1$. The sequence is as follows:

$0, 1, 1, 2, 3, 5, 8, 13, 21, ...$

```{r}
fibonacci<-function(n)
{
  if(n==0 | n==1){  #Base case
    return(n)
  }
  return(fibonacci(n-1)+fibonacci(n-2))  #Recursive case
}
#The function `fibonacci` prints the n+1th term of the fibonacci sequence when `n` is passed as an argument. Thus, we need to reduce `n` by 1 to print the nth term of the sequence. The function `nth_term` reduces `n` by 1 before passing `n` to the function `fibonacci()`.
nth_term<-function(N)
{
  fibonacci(N-1)
}
nth_term(7)
```

### Practice exercise 1

Write a recursive function that computes the sum of squares of the first $N$ natural numbers, where $N$ is a parameter to the function.

```{r}
#| eval: false
squares<-function(N)
{
  if(N==1)  #Base case
  {
    return(1)
  }else{    #Recursive case
    return(N**2+squares(N-1))
  }
}
squares(10)
```

### Practice exercise 2

Write a function that counts the occurrence of digit $k$ in a given integer $n$ using recursion. The function has $n$ and $k$ as parameters.

```{r}
#| eval: false
freq_digits<-function(n,d)
{
  if(n==0)
  {
    return(0)
  }
  digit = n%%10
  n_int = as.integer(n/10)
  if(digit==d)
  {
    return(1+freq_digits(n_int,d))
  }
  return(freq_digits(n_int,d))
}
freq_digits(8670800,0)
```

### Practice exercise 3

Use recursion to write a function that accepts a word as an argument, and returns `TRUE` if the word is a palindrome, otherwise returns `FALSE`.

```{r}
#| eval: false
word<-'racecar'
palindrome<-function(word)
{
  if(nchar(word)<=1)
  {
    return(TRUE)
  }else if(substr(word,1,1)==substr(word,nchar(word),nchar(word)))
  {
    palindrome(substr(word,2,nchar(word)-1))
  }else{
    return(FALSE)
  }
}
palindrome(word)
```

## Recursion vs iteration

Recursion is typically used when the problem is naturally recursive (for e.g., generating a Fibonacci sequence), or the data is naturally recursive ( for e.g., filesystem). Recursive solutions can be easy to read and understand as compared to the corresponding iterative solution.

One downside of recursion is that it may take more space than an iterative solution. Building up a stack of recursive calls consumes memory temporarily, and the stack is limited in size, which may become a limit on the size of the problem that the recursive implementation can solve.