Recursion

Recursion is a technique in which a function calls itself. It is the process of iterating over a technique by breaking down problems.

In a recursive function, two conditions are important:

• Base case/condition
• Recursive case/condition

Base case

The base case is the simplest of the problems where recursion stops. In this case, the result is returned immediately.

Recursive case

In this case, the function calls itself, breaking the problem down until the base case is reached.

Without a base case, the recursive case runs in an infinite loop until 'maximum call stack size exceeded'.

Examples

• Factorial

A factorial is a function that multiplies a number by every number below it i.e 5! = 5 x 4 x 3 x 2 x 1

5! = 5 x 4! = 5 x 4 x 3! = 5 x 4 x 3 x 2! = 5 x 4 x 3 x 2 x 1!

P.S. 0! is 1

A recursive function can be used to solve a factorial as in below

const factorial = (n) => { 
if(n === 0){    //base case(this condition stops the recursion)
        return 1
  }
 else if(n > 0){
        let result = n * factorial(n-1)
        return result
  }
}

• Fibonacci

Fibonacci sequence is a sequence of numbers in which a number is a sum of the two numbers preceding it, starting from 0 and 1. A recursive function can be used to generate a Fibonacci sequence as written below, where n is the Fibonacci number

const fibonacci = (n) => {
    if(n === 1){     
        return  [0,1] //base case
    }
    else{
        let fibSeq = fibonacci(n-1)
        fibSeq.push( fibSeq[fibSeq.length - 1] + fibSeq[fibSeq.length - 2] ) //recursive case
        return fibSeq
   }
}

• Summation

Addition of a series of numbers. The summation function below is a recursive function used to add up numbers in an array.

const summation = (arr) => {

    if(arr.length === 1){ 
        return arr[0]  //base
    }
    else{ 
        let sum = arr[arr.length-1] + summation(arr.slice(0, arr.length-1)) //recursion
        return sum
    }
}

• Count down

The countDown function is used to generate a countdown in the array count.

let count = []
const countDown = (n) => {
    if(n <= 0){
        return//base
    }else{
        count.unshift(n)
        countDown(n-1) //recursive
        return count
    }
}

Recursion vs iteration

Generally, recursive functions are readable but iteration is usually a faster way of solving problems than using recursion. Recursion takes more memory space than iteration by building a stack, making recursion slower than iteration.