Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Key Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Recursion

What is Recursion?

Recursion is the process on which a function calls itself, either in a direct or indirect way. Is worth noting that every problem that can be solved iteratively can also be solved recursively.

public class Example {
// function which returns an integer
    int recursion(int n) {
        if (n == 0) return 0;
        return n + recursion(n-1); // <— Function calling itself. That is recursion.
    }
}

In this example we can see that the function is calling itself, every time there is a call to the function the number being passed down is reduced by one. Imagine we call the function originally with a 5, the first time around it will be called like this:

recursion(5);
recursion(4);
recursion(3);
recursion(2);
recursion(1);

Eventually it will meet the base condition which tends to be an if statement or similar approach, which will prevent an infinite recursive call (an eventually a stack overlow error). In this case we are doing the sum of all the numbers - starting from the one we added as an input; 5 + 4 + 3 + 2 + 1 + 0 = 15.

Let’s see another example, getting the factorial of a number. The factorial is the multiplication of every number below the passed number and is represented with a !. For example the Factorial of 5 would be represented as 5! and it would be like this: 5 * 4 * 3 * 2 * 1 = 120.

int factorial(int n) {
    if (n <= 0) {
        return 1;
    }
    return n * solution(n-1);
}

image

Advantages of recursion

Using recursive algorithms certain problems can be solved elegantly and easily, in comparison to iterative algorithms - which also tend to be easier to understand, debug and mantain.

Popular known problems such as Towers of Hanoi, tree traversals, graphs, depth first search, etc. Are great examples on the effectiveness of recursion as we will see in the next chapters.

Disadvantages of recursion

A recursive algorithm has greater space requirements than iterative program as all functions will remain in the stack until the base case is reached. It also has greater time requirements because of function calls and returns overhead.

Tailed and non-tailed recursion

A recursive function is tail recursive when the call is the last thing executed by the function. This is important as tail recursive functions are considered better than non tail recursive functions, as they can be optimised by the compiler. The compilers can detect when the tail recursive call is the last statement - meaning there is nothing left to do in the current function hence saving the current function frame in the stack.

The Factorial example just shown is not tail recursive as the value returned is factorial(n-1) and the last thing done is not factorial(n).

We could write the same function in a tail recursive fashion - by passing one more argument into the function which would get the accumulative value of the factorial, then when n reaches 0 it would return the accumulated value.

static int factTR(int n, int a) {
    if (n == 0) return a;

    return factTR(n - 1, n * a);
}

// A wrapper over factTR
static int fact(int n) {
    return factTR(n, 1);
}
Last updated on 3/8/2020
← SearchingDynamic Programming →
  • What is Recursion?
  • Advantages of recursion
  • Disadvantages of recursion
  • Tailed and non-tailed recursion
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr