1.6 Recursive Functions

Motivation:

• In R, there are 3 ways to create a repetitive execution:
  • while
  • for
  • repeat
• There is also an alternative way to perform a set of tasks without using the common loop structures

Definition 1.6 A function is called recursive if the body of the function calls the function itself, either directly or indirectly.

That is, the process of executing the body of a recursive function may in turn require applying that function again. Recursive functions do not use any special syntax in R, but they do require some effort to understand and create.

FUNCTION recursive(x): 
    BASE CASE: 
        RETURN some value for some condition
    RECURSIVE CASE: 
        RETURN call recursive(x) with computation

When designing recursive functions, we look for ways in which a problem can be broken down into simpler problems.

Recursion is often the natural approach for problems defined in terms of smaller subproblems of the same type (e.g., divide-and-conquer problems).

Example 1: Factorial

Using a for loop:

factorial_loop <- function(n) { 
    result <- 1 
    for (i in 1:n) { 
        result <- result * i } 
    return(result) 
}

To understand recursion, we first consider: What is the basic task in getting the factorial of a number?

• Multiplying a sequence of integers:

  $$n! = n\times(n-1)\times(n-2)\times\cdots\times1$$

• or… multiplying $n$ by the factorial of the previous number:

  $$n! = n\times(n-1)!$$

A common pattern can be found in the body of many recursive functions.

The body begins with a base case, a conditional statement that defines the behavior of the function for the inputs that are simplest to process.

The base case is followed by one or more recursive calls that

• simplify the original problem.

• express computation by simplifying problems incrementally

factorial_recursive <- function(n) {
        if (n <= 1) {       # base case
            return(1)  
        }else{              # recursive call
            return(n * factorial_recursive(n - 1))
        }
}

For example:

• $4!$ may be easier to compute than $5!$ Therefore, we solve $4!$ first then multiply it by 5.

• But $3!$ is also easier than $4!$, so we multiply $3!$ by $4$ to get $4!$

• And so on…

Recursive function vs Loops

Recursive functions often solve problems in a different way than the iterative approaches. Consider the example of taking the factorial of a natural number:

factorial_loop <- function(n) { 
    result <- 1 
    for (i in 1:n) { 
        result <- result * i 
    } 
    return(result) 
}

Iterative implementation by using a for statement accumulates the result by multiplying together each positive integer i up to n.

Difference?

How do factorial_loop and factorial_recursive differ?

They differ conceptually:

• The iterative function factorial_loop constructs the result from the base case of 1 to the final total by successively multiplying in each term.

• The recursive function factorial_recursive, on the other hand, constructs the result directly from the final term, n, and the result of the simpler problem, fact(n-1).

Example 2: sum of the digits of a natural number

Preliminary Exercise: Write a function that sums the digits of a natural number

Note that the sum of the digits of $1234$ is: $$1 + 2 + 3 + 4 = 10$$

Now, if we separate the last digit and the all-but-last digits: - The sum of the digits of the all-but-last digits ($123$) is: $$1 + 2 + 3 = 6$$ - And the sum of the all-but-last-digits plus the last digit is : $$6 + 4 = 10$$ Still $10$!

• But how do we get the sum of all-but-last-digit?

Implement this pseudocode in R:

BEGIN
    INPUT n
    sum ← 0
    WHILE n > 0 
        digit ← n MOD 10     # Extract the last digit 
        sum   ← sum + digit  # Add digit to the sum
        n     ← n INTDIV 10  # Remove the last digit 
    END LOOP
    RETURN sum
END

Did you see the pattern?

We are adding the last digit to the sum of digits of the all-but-last-digits, until there is none left to remove.

This separation gives us an algorithm to sum the digits of a number n:

• add its last digit n %% 10 to the sum of the digits of n%/%10.

• The sum of the digits of n%/%10 can be computed as well using the same function

There’s one special case: if a number has only one digit, then the sum of its digits is itself.

To summarize:

1. Input: n=1234
   • 1234 %% 10 = 4 (last digit)
   • 1234 %/% 10 = 123 (remaining digits)
2. Recursive Steps:
   • SumOfDigits(1234)= 4 + SumOfDigits(123)
   • SumOfDigits(123) = 3 + SumOfDigits(12)
   • SumOfDigits(12) = 2 + SumOfDigits(1)
   • SumOfDigits(1) = 1 (base case: output n if n < 10)
3. Calculation: SumOfDigits(1234) = 10

Now, creating the recursive function SumOfDigits()

SumOfDigits <- function(n){
    if(n < 10){
        return(n)
    } else{
        last      <- n %% 10
        remaining <- n %/% 10
        return(1 + SumOfDigits(remaining))  
    }
  }

1.6.1 General Tips for Writing Recursive Functions

1. Identify the Base Case:

   This is the condition where the recursion stops. Without it, the function will run infinitely and lead to a stack overflow.

2. Define the Recursive Case:

   This is where the function calls itself with modified parameters to solve smaller subproblems.

3. Ensure Progress Towards the Base Case:

   Each recursive call should bring the parameters closer to the base case.

1.6.2 Mutual Recurssion

The simplest examples of recursion, including most of those discussed here, illustrate direct recursion, where a function calls itself.

In contrast, indirect recursion occurs when a function is invoked not by itself but by another function it has called, either directly or indirectly.

For instance, if function f calls itself, that is direct recursion.

However, if f calls g, which then calls f, this constitutes indirect recursion for f.

Indirect recursion is also called mutual recursion.

As an example, consider the following definition of even and odd for non-negative integers:

• a number is even if it is one more than an odd number;

• a number is odd if it is one more than an even number; and

• 0 is even.

Using this definition, we can implement mutually recursive functions to determine whether a number is even or odd.

is_even <- function(n){
  if(n == 0){
    return(TRUE)
  }else{
    return(is_odd(n - 1))
  }
}

is_odd <- function(n){
  if(n == 0){
    return(FALSE)
  }else{
    return(is_even(n - 1))
  }
}

is_even(4)

## [1] TRUE

Mutually recursive functions can be turned into a single recursive function by breaking the abstraction boundary between the two functions.

In this example, the body of is_odd can be incorporated into that of is_even, making sure to replace n with n - 1in the body ofis_odd` to reflect the argument passed into it.

is_even <- function(n){
  if(n == 0){
    return(TRUE)
  }else{
    if(n - 1 == 0){
      return(FALSE)
    }else{
      return(is_even((n-1)-1))
    }
  }
}

is_even(420)
is_even(69)

## [1] TRUE
## [1] FALSE

1.6.3 Printing in Recursive Functions

The computational process implemented by a recursive function can often be visualized using calls to print.

As an example, we will implement a function cascade that prints all prefixes of a number from largest to smallest.

cascade <- function(n){
  # Print a cascade of prefixes of n.
  if(n < 10){
    print(n) 

  }else{
    print(n)
    cascade(n%/%10)
    print(n)
  }
}

cascade(2021)

## [1] 2021
## [1] 202
## [1] 20
## [1] 2
## [1] 20
## [1] 202
## [1] 2021

In this recursive function, the base case is a single-digit number, which is printed (not necessarily return). Otherwise, a recursive call is placed between two calls to print.

Should the base case always come before the recursive calls?

It is not a strict requirement that base cases be expressed before recursive calls. In fact, this function can be expressed more compactly by observing that print(n) is repeated in both clauses of the conditional statement, and therefore can precede it.

cascade <- function(n){
  # Print a cascade of prefixes of n.
  print(n)

  if(n >= 10){
    cascade(n%/%10)
    print(n)
  }
}

cascade(2021)

## [1] 2021
## [1] 202
## [1] 20
## [1] 2
## [1] 20
## [1] 202
## [1] 2021

Which is faster in computing time, iterative functions or recursive functions?

• Iterative functions are still generally faster than recursive functions and all recursive functions can be implemented using iteration.

• In some cases, recursive functions are easier to code than their iterative counterparts; they simplify the coding process.

Practice Exercise

1. Sum of a sequence

   Using only simple addition, Boolean logic, and control structures, write a function using recursion that returns the sum of all whole numbers from 1 to n. $$\sum_{i=1}^n i$$ Name the function sum_recur that takes in the argument n.

   sum_recur(5)

   ## [1] 15

2. Sum of a function of sequence

   Recall discussions on higher-order functions, where we can also take functions as arguments. Create a function sum_recur_f with parameter f that gets the sum of a function of a sequence of natural numbers from 1 to n.

   $$\sum_{i=1}^n f(i)$$

   sum_recur_f(function(x){x^2}, 4)

   ## [1] 30

3. Fibonacci

   Obtain the $n^{th}$ Fibonacci number using Recursive Function named Fibonacci with parameter n. $$0, 1, 1, 2, 3, 5,…$$

   Hints:

   • There are 2 base cases (n==1 and n==2) which will return $0$ or $1$ respectively. Make use of the else if structure.

   • In the recursive call, you may call Fibonacci(.) twice.

   • To get the $n^{th}$ Fibonacci number, add the $(n-1)^{th}$ and $(n-2)^{th}$ Fibonacci numbers.

   Fibonacci(4)
   Fibonacci(5)
   Fibonacci(6)
   Fibonacci(7)

   ## [1] 2
   ## [1] 3
   ## [1] 5
   ## [1] 8