Recursion Algorithms - Interview Questions

Recursion is an approach to solving algorithms by using a function that calls itself. This process in which a function calls itself is called recursion, and the function that calls itself is called a recursive function.

How does recursion work?

Every time the recursive function is called, the main problem is reduced into a sub-problem. The recursion continues until the sub-problem can be solved without calling the recursive function. This is called the base condition.

Hence, a recursive function must have two conditions to prevent an infinite loop

1. Base condition - where the answer can be derived without calling the recursive function. This is how a recursive function terminates the loop in which it calls itself.

2. Recursive condition - Condition that reduces the problem into a sub-problem and calls the recursive function.

Problems that can be solved using recursion

Many problems can be effectively solved using recursion. Some examples are Towers of Hanoi, Tree traversals, DFS of graphs etc.

Write a function in Java that returns the factorial of a number n?

 FAQ

Factorial of a number n, written as 'n!', is the product of all positive numbers less than n.

Formula: n! = n*(n-1)*(n-2)*(n-3)*(n-4)...*1

Example of sequence: 4! = 4*3*2*1=24

Below function calculates the factorial for a number n using recursion.

public int factorial(int n) {
 //base condition
 if (n==0) {
  return 1;
 } else {
  //recursion
  return n*factorial(n-1);
 }
}

Write a function in Java that returns the factorial of a number n?

 FAQ

Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones.

Formula: Fn = Fn-1 + Fn-2

Example of sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

function fibonacci(int n) {
 //base condition
 if (n <= 2) {
  return 1;
 }
 //recursion
 return fibonacci(n — 1) + fibonacci(n — 2);
}
 
Subscribe to our Questions

 

Algorithms - Interview Questions

Basics of AlgorithmsRecursion AlgorithmsGraph Algorithms
 
MASTER Algorithms  

Top ranked courses to help you master Algorithms skills.
Master the Coding Interview: Data Structures + Algorithms

iconicon

Offered By - Andrei Neagoie
Platform - Udemy
Rating - * * * * *
Students Enrolled - 100,000 +

Algorithms

iconicon

Offered By - Princeton University
Platform - Coursera
Rating - * * * * *
Students Enrolled - 850,000 +

RECOMMENDED RESOURCES
Behaviorial Interview
Top resource to prepare for behaviorial and situational interview questions.

STAR Interview Example