Jonathan Thomas

Posted on Jul 17, 2019

Recursion recall, because it's necessary

#computerscience #beginners #algorithmsanddatastructures #interviewprep

Continuing on since my last post on Big O, which involves time and space complexity of programs, I'm adding a quick recall of an often used, if not completely understood concept. RECURSION!

What it do?

Recursion, in the most basic terms ,is a function that has the ability to call itself.It is used all the time in in programming and is seen as a cleaner alternative to iteration.

With recursion, you use a different input each time until you reach your base case.

For example, you have an array of numbers and you want to find out which of the elements are odd. So knowing that even numbers are anything divisible by two with no remainder, I can say my base case is
N%2 where N is an element in the array divided by two with no remainder.

I could put this in a helper function that uses this as the base case when no matter what my inputs. We need a base case and different inputs to ensure that program returns the base case when conditions are met.

So this was my quick recall of recursion. I will come back and post an updated version as I learn more. Constructive criticism is greatly appreciated and hopefully this helps you too.

Thanks for reading.....k bye :)

Top comments (4)

Curtis Fenner • Jul 18 '19

Your explanation needs to be clarified, because I don't see what the recursive case is. Which function would be invoking itself?

Jonathan Thomas • Jul 18 '19

Thank you for pointing that out. Going back to the find all even number example say I'll write a fucntion find all odd number *NOTE: code example used from Colt Steele's Javascript Algorithms and Data Structures Mastercass *

function collectOddValues(arr){

let result = []

function helper(helperInput){
    if(helperInput.length === 0) {
        return;
    }

    if(helperInput[0] % 2 !== 0){
        result.push(helperInput[0])
    }

    helper(helperInput.slice(1))
}

helper(arr)

return result;

In this code the helper function makes ensures that there if there is no element given it exits out. The base case of the helper function is that it checks the zeroth item in the array set and checks to see if it's divisible by 2 with no remainder. If that condition is met, the element is cut from the array and the next element in the array is assessed until there are only odd elements left or there are no more elements

Next here's another code example for pure recursion *NOTE: code example from Colt Steele's Javascript Algorithms and Data Structures Masterclass *

function collectOddValues(arr){
let newArr = [];

if(arr.length === 0) {
    return newArr;
}

if(arr[0] % 2 !== 0){
    newArr.push(arr[0]);
}

newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;

}

Here we're declaring a an empty array gets returned if there's nothing in the inputs. For our bas case we again check the zeorth element to see if results in an odd number and if that is the case, it gets pushed into a new array of odd values that gets sliced from the input once the collectOddValues function is called.

Hopefully I'm on the right track with this explanation and clarified what I missed. More feedback is appreciated and I hope this helps :)

Curtis Fenner • Jul 18 '19

What was missing was what you are recursing on, which is the tail of the input list. With the example code the recursion makes sense.

However, the "base case" isn't what you said -- the base case is the if (are.length == 0) {, which doesn't have anything to do with whether numbers are odd or even. This is what three me off.

Jonathan Thomas • Jul 18 '19

Thanks for that I'll be more careful in the future

DEV Community

Recursion recall, because it's necessary

Top comments (4)

Read next

Creating a textarea character limit indicator

CSS SPECIFICITY?

🦀 Axum - Hello World !

Mastering SQL Queries: A Comprehensive Guide for Beginners