11  R: Recursion

11.1 Recursion

Recursion is a method of solving a problem by dividing it into smaller instances of the same problem. Recursion solves such problems by using functions that call themselves from within their own code. This forms a loop, where every time the function is called, it calls itself again and again. However, every time the function calls itself, it checks certain condition(s) which are the stopping condition(s). When such condition(s) are true the function will stop calling itself. These conditions are called the base case of the recursive function.

Every recursive function must have at least two cases:

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.

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

[1] 120

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, ...\)

fibonacci <- function(n) {
  # Base case
  if (n == 0 | n == 1) return(n)
  
  #Recursive case
  return(fibonacci(n - 1) + fibonacci(n - 2))  
}
#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)

[1] 8

11.1.1 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.

squares <- function(N)
{
  
  # Base case
  if(N == 1)  return(1)
  
  # Recursive case
  return(N ** 2 + squares(N - 1))
}
squares(10)

11.1.2 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.

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)

11.1.3 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.

word<-'racecar'
palindrome <- function(word) {
  if(nchar(word) <= 1) return(TRUE)
  if(substr(word, 1, 1) == substr(word, nchar(word), nchar(word))) {
    palindrome(substr(word, 2, nchar(word) - 1))
  } else return(FALSE)
}
palindrome(word)

11.2 Space occupied by recursive calls

Stack memory is a memory usage mechanism that allows the system memory to be used as temporary data storage that behaves as a first-in-last-out buffer.

When a recursive function is called in a programming language, the stack memory is used to keep track of each invocation of the function. Let’s break down how stack memory is occupied during the execution of a recursive function:

11.2.1 Function Call

When a recursive function is called, a new stack frame is created on the call stack. The parameters, local variables, and return address are stored in this stack frame.

11.2.2 Nested Calls

If the recursive function makes another call to itself, a new stack frame is created for the new invocation. This process continues as long as the base case is not reached.

11.2.3 Stack Frames in Memory

Each stack frame is pushed onto the top of the call stack, forming a chain of frames. The stack grows deeper with each recursive call.

11.2.4 Local Variables and Parameters

Each invocation has its own set of local variables and parameters stored in its respective stack frame. These values are separate and independent for each level of recursion.

11.2.5 Return Addresses

The return address of each invocation is stored in its stack frame. When a function call completes, the program knows where to return by using this address.

11.2.6 Base Case

The recursion continues until the base case is reached. The base case is a condition that, when met, stops the recursive calls and starts unwinding the call stack.

11.2.7 Unwinding the Stack

• As the base case is reached, the recursive calls start to complete, and the stack frames are popped off the call stack.

• The return values are used to compute the final result as the stack unwinds.

11.2.8 Memory Deallocation

• As each stack frame is popped off, the memory occupied by that frame is deallocated.

• This process continues until the initial function call is reached.

The function CStack_info() can be used to retrieve the stack memory occupied by the recursive calls. If the function is recursively called so many times such that the stack usage limit is reached, the program stops indicating a stack overflow error.

11.3 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.

In the factorial examples below, we compare the stack memory occupied in case of recursion and iteration. Note that the space occupied continues to increase in case of recursion while remains a constant in case of iteration. The units of the size and current attributes are bytes.

# Finding factorial of an integer with recursion

factorial_recursion <- function(n) {
  
  if (n == 1) return(1)    
  print(Cstack_info())
  return(n * factorial(n - 1)) 
}
factorial_recursion(5)

      size    current  direction eval_depth 
  15938355     341440          1         40 

[1] 120

# Finding factorial of an integer with iteration

factorial_iteration <- function(n) {
  fac <- 1
  for (i in 1:n) {
    fac <- fac*i
    print(Cstack_info())
  } 
  return(fac)
}
factorial_iteration(5)

      size    current  direction eval_depth 
  15938355     359872          1         39 
      size    current  direction eval_depth 
  15938355     359872          1         39 
      size    current  direction eval_depth 
  15938355     359872          1         39 
      size    current  direction eval_depth 
  15938355     359872          1         39 
      size    current  direction eval_depth 
  15938355     359872          1         39 

[1] 120

11.3.1 Time Complexity

• There are \(O(N)\) recursive calls in our recursive approach, and each call uses \(O(1)\) operations. Thus, the time complexity of factorial using recursion is \(O(N)\).

• There are \(O(N)\) iterations of the loop in our iterative approach, so its time complexity is also \(O(N)\).

Though both the programs’ theoretical time complexity is the same, a recursive program will take more time to execute due to the overhead of function calls, which is much higher than that of iteration.

11.3.2 Space Complexity

• In the recursive program, due to each recursive call, some memory gets allocated in the stack to store parameters and local variables. As there are \(O(N)\) recursive calls, the space complexity using recursion is \(O(N)\).

• No extra memory gets allocated in the iterative program, so its space complexity is \(O(1)\).

11.3.3 Strengths and Weaknesses of Recursion and Iteration

11.3.3.1 Iteration

Strengths:

• Iteration can be used to repeatedly execute a set of statements without the overhead of function calls and without using stack memory.

• Iteration is faster and more efficient than recursion.

• It’s easier to optimize iterative codes.

Weaknesses:

• In loops, we can go only in one direction, i.e., we can’t go or transfer data from the current state to the previous state that has already been executed.

• It’s difficult to traverse trees/graphs using loops.

11.3.3.2 Recursion

Strengths:

• It’s easier to code the solution using recursion when the solution of the current problem is dependent on the solution of smaller similar problems.

• Recursive codes are smaller and easier to understand.

• We can pass information to the next state in the form of parameters and return information to the previous state in the form of the return value.

• It’s a lot easier to perform operations on trees and graphs using recursion.

Weaknesses:

• The simplicity of recursion comes at the cost of time and space efficiency.

• It is much slower than iteration due to the overhead of function calls and control shift from one function to another.

• It requires extra memory on the stack for each recursive call. This memory gets de-allocated when function execution is over.

• It is difficult to optimize a recursive code, and they generally have higher time complexity than iterative codes due to overlapping sub-problems.