Skip to main content

Recursion Common Problems


Recursion 

Recursion basically is function calling itself, when you call a function - from another function i.e functionA() calling functionB() or functionC() calling itself, it will create an stack, and the idea of calling functionX() is basically solving the smaller problems or solving the problems with small use case or inputs. Recursion technique is widely used if you want to Break the problem into small usecases and use the result or the output of the usecase to solve the larger problem. 

lets take an example - Factorial of the number n! ? the nth factorial would be        n!= n * (n-1)! example  5! = 5 * 4! 

Different Algorithms where the recursion is used extensively

1. Divide and Conquer

2. Backtracking

3. Tree Data structure - iteration  

Common Steps of recursion  

The first step is to identify the Base case, The base case defines the edge case or the smallest part of the problem, beyond which you cannot break the problem, example in case of the factorial function base case will be ZERO or ONE.

 The Hypothesis i.e. The reasoning - how do we want to break this problem ?

Induction - solving the problem. 




Problems 

1. Josephus problem (Reduction Problem) - this is an very popular problem, there are many techniques for solving the problem, but lets try to solve this problem using recursion. 


2. Tower of Hanoi (Move from A -> B )- 

Base case ? The base case is the last pending disk that needs to be moved to destination 

3. Knapsack problem (The Choice / Decision tree)

4. Generate all subsequences (Decision Tree + )

5. Generate all the permutation of String (Backtracking) 

6. Knapsack problem using the Dynamic Programming

 




    





1. IBH - Induction Base Hypothesis

2. Choice Diagram,  i.e. create the decision tree




 1. Tower Of Hanoi

2. All Permutation of Strings 

3. No of ways to reach from Point A to Point B using the GRID

4. Knapsack - Bounded & unbounded 

5. Sliding Window problem 





Comments

Post a Comment

Popular posts from this blog

Hexagonal Architecture (Ports & Adapters Pattern)

Hexagonal Architecture , also known as the Ports and Adapters pattern, is a software design pattern that aims to create a decoupled and maintainable application by separating the core business logic from external concerns (like databases, APIs, and UIs). Structure of Hexagonal Architecture A typical Hexagonal Architecture has three main layers: 1️⃣ Core Domain (Application Logic) This contains the business rules and domain models. It is completely independent of external technologies . Example: If you’re building a banking system , this part would include logic for transactions, withdrawals, and deposits . 2️⃣ Ports (Interfaces) These are interfaces that define how the core interacts with external components. Two types of ports: Inbound Ports (driven by external inputs like APIs, UI, or events) Outbound Ports (used to interact with external services like databases, messaging systems, etc.) 3️⃣ Adapters (Implementation of Ports) These are concrete implementations of the ports, re...
Post a Comment
Read more

Recursion & Choice

Understanding Recursion and Choice Diagrams with Examples Understanding Recursion and Choice Diagrams with Examples Recursion is a powerful concept in programming where a function calls itself to solve smaller instances of the same problem. It's often used in solving complex problems that can be broken down into simpler subproblems. In this blog post, we'll explore the basics of recursion, understand choice diagrams, and see examples to illustrate these concepts. What is Recursion? Recursion occurs when a function calls itself directly or indirectly to solve a problem. A recursive function must have a base case to terminate the recursive calls and prevent infinite recursion. Here's a simple example of a recursive function to calculate the factorial of a number: public class RecursionExample { public static void main(String[] args) { int number = 5; int result = factorial(...
Post a Comment
Read more

Frameworks

  Communication Frameworks: BLUF:  Google's culture strongly emphasizes efficiency and directness, so getting to the "bottom line up front" is very common. SCQA:  Used in presenting proposals, making recommendations, and structuring project plans. PAS : Used in selling ideas and influencing others. BAB : Used in selling ideas and influencing others. Sparklines : Used in presentation to influence others. STAR:  Widely used in Google's interview process and performance evaluations. Problem-Solving/Decision-Making Frameworks: 5 Whys:  A fundamental technique for root cause analysis, and Google is known for its emphasis on data-driven decision-making, which often involves digging into the root causes of problems. Systems Thinking:  Given the complexity of Google's systems, a systems thinking approach is essential. The Four Questions : Used in post-mortem to review an incident. Human factors : Used in post-mortem to avoid the blame culture. Time Management/Prior...
Post a Comment
Read more