thiscodeWorks - Organizing the best of code online

#c++ #dsa #linkedlist #reverselinkedlist #recursion #circular

// check if a linked list is circular or not
bool isCircular (node* head) {
  if (head == NULL) {
    return true;
  }
  node* temp = head -> next;
  while (temp != NULL && temp != head) {
    temp = temp -> next;
  }
  if (temp == head) {
    return true;
  }
  return false;
}

#c++ #dsa #linkedlist #reverselinkedlist #recursion

code to reverse a linked list in the group of k

node* kReverse (node* head, int k) {
  // base case
  if (head == NULL) {
    return NULL;
  }

  // step 1: reverse first k nodes
  node* forward = NULL;
  node* curr = head;
  node* prev = NULL;
  int cnt = 0;
  while (curr != NULL && cnt < k) {
    forward = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forward;
    cnt++;
    
  }
  // step 2: recursion
  if (forward != NULL) {
    head -> next = kReverse(forward, k);
    
  }
  // step 3: return head of the modified list
  return prev;
}

#c++ #dsa #linkedlist #reverselinkedlist #recursion #middlenode

return the middle node in linked list and in the case of two node return the further one from head

int getLength (node* head) {
  int length = 0;
  node* temp = head;
  while (temp != NULL) {
    length++;
    temp = temp -> next;
  }
  return length;
}

node* middleNode (node* head) {
  int length = getLength(head);
  int mid = (length/2) + 1;
  int cnt = 1;
  node* temp = head;
  while (cnt < mid) {
    temp = temp -> next;
    cnt++;
  }
  return temp;
}

#c++ #dsa #linkedlist #reverselinkedlist #recursion

reverse linked list using recrsion

node* reverseLinkedList (node* & head) {
  //empty list or single node
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* prev = NULL;
  node* curr = head;
  node* forword = NULL;
  while (curr != NULL) {
    forword = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forword;
  }
  return prev;
}

#c++ #dsa #linkedlist #reverselinkedlist #recursion

reverse linked list using recursion

// it will return the head of the reversed linked list
node* reverse1 (node* head) {
  // base case
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* chotaHead = reverse1(head -> next) {
    head -> next -> next = head;
    head -> next = NULL;

    return chotaHead;
  }
}

#c++ #dsa #recursion #string #mergesort

merge sort using recursion

void merge(int *arr, int s, int e) {
  int mid = s + (e - s) / 2;
  int len1 = mid - s + 1;
  int len2 = e - mid;
  int *first = new int[len1];
  int *second = new int[len2];

  // copy vales
  int mainArrayIndex = s;
  for (int i = 0; i < len1; i++) {
    first[i] = arr[mainArrayIndex++];
  }
  mainArrayIndex = mid + 1;
  for (int i = 0; i < len2; i++) {
    second[i] = arr[mainArrayIndex++];
  }

  // merge 2 sorted arrays
  int index1 = 0;
  int index2 = 0;
  mainArrayIndex = s;
  while (index1 < len1 && index2 < len2) {
    if (first[index1] < second[index2]) {
      arr[mainArrayIndex++] = first[index1++];
    } else {
      arr[mainArrayIndex++] = second[index2++];
    }
  }
  while (index1 < len1) {
    arr[mainArrayIndex++] = first[index1++];
  }
  while (index2 < len2) {
    arr[mainArrayIndex++] = second[index2++];
  }
}

void mergeSort(int *arr, int s, int e) {
  if (s >= e) {
    return;
  }
  int mid = s + (e - s) / 2;
  // left  part
  mergeSort(arr, s, mid);
  // right part
  mergeSort(arr, mid + 1, e);
  // merge
  merge(arr, s, e);
}

#c++ #dsa #recursion #string #palindrome #checkpalindrome

code to check palindrome using recursion

bool checkPalindrome (string s, int start, int length) {
  if (start>length) {
    return true;
	}
  if (s[start] != s[length]) {
    return false;
	}
  else {
    return checkPalindrome(s,start+1,length-1;)
  }
}

#c++ #dsa #recursion #sorting #string #ratinamazeproblem

rat in a maze problem

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool isSafe(int x, int y, int n, vector<vector<int>> visited,
            vector<vector<int>> &m) {
  if ((x >= 0 && x < n) && (y >= 0 && y < n) && visited[x][y] == 0 &&
      m[x][y] == 1) {
    return true;
  } else {
    return false;
  }
}

void solve(vector<vector<int>> &m, int n, vector<string> &ans, int x, int y,
           string path, vector<vector<int>> visited) {
  // you have reached x,y here

  // base case
  if (x == n - 1 && y == n - 1) {
    ans.push_back(path);
    return;
  }
  visited[x][y] = 1;

  // 4 choices D,L,R,U
  // down

  int newx = x + 1;
  int newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('D');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // left

  newx = x;
  newy = y - 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('L');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // right

  newx = x;
  newy = y + 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('R');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // up

  newx = x - 1;
  newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('U');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  visited[x][y] = 0;
}

vector<string> findPath(vector<vector<int>> &m, int n) {
  vector<string> ans;
  if (m[0][0] == 0) {
    return ans;
  }
  int srcx = 0;
  int srcy = 0;

  vector<vector<int>> visited = m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      visited[i][j] = 0;
    }
  }

  string path = "";
  solve(m, n, ans, srcx, srcy, path, visited);
  sort(ans.begin(), ans.end());
  return ans;
}

int main() {
  int n = 4;
  vector<vector<int>> m = {
      {1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
  vector<string> ans = findPath(m, n);
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}

#c++ #dsa #recursion #sorting #array #arraysorting #bubblesorting

bubble sorting of the array using recursion.

void sortArray (int *arr, int n) {
  if (n==0||n==1)
    return;
  for (int i=0; i<n-1; i++) {
    if (arr[i]>arr[i+1]) {
      swap(arr[i],arr[i+1]);
    }
  }
  sortArray(arr,n-1);
}

#c++ #dsa #recursion #math

power of function using recursion.

int power (int a, int b) {
  if (b==0)
    return 1;
  if (b==1)
    return a;
  int ans = power(a,b/2);
  if (b%2==0)
    return ans*ans;
  else
    return a*ans*ans;
}

#c++ #dsa #recursion #array #binarysearch

binary search using recursion

bool binarySearch(int arr[], int s, int e, int key) {
  if (s > e)
    return false;
  int mid = s + (e - s) / 2;
  if (arr[mid] == key)
    return true;
  if (arr[mid] < key)
    return binarySearch(arr, mid + 1, e, key);
  else
    return binarySearch(arr, s, mid - 1, key);
}

#c++ #dsa #recursion #array #linearsearch

linear search using recursion.

bool linearsearch (int *arr, int size, int key) {
  if (size == 0)
    return false;
  if(arr[0]==key)
    return true;
  else 
    return linearsearch(arr+1, size-1, key);
}

#c++ #dsa #recursion #array

check if array is sorted using recursion.

bool isArraySorted (int arr[],int size) {
  if (size == 0 || size == 1) 
    return true;
  if (arr[0]>arr[1]) 
    return false;
  else {
    bool remainingPart = isArraySorted(arr+1,size-1); 
    return remainingPart;
  }
  
}

#c++ #dsa #fibonacci #recursion

nth fibonacci number using recursion

class Solution {
public:
    int fib(int n) {
        if (n==0)
        return 0;
        if (n==1)
        return 1;
        return fib(n-1)+fib(n-2);
        
    }
};

#recursion #python

Count no of Partitions of size at most m

def count_partitions(n, m):
  if (n == 0 ): 
    return 1 # there is only 1 way i.e. to leave it unpartitioned
  if (m == 0 or n < 0):
    return 0 # there is no way to divide n into 0 partions or if n is -ve (latter one from edge case of recursion call of n - m)
  else:
    return count_partitions(n - m, m) + count_partitions(n, m - 1)

print(count_partitions(9, 5)) # 23

#recursion #python

Unique Paths

def uniquePaths(n, m):
  if (n == 1 or m == 1):
    return 1
  else:
    return uniquePaths(n - 1, m) + uniquePaths(n, m - 1)

print(uniquePaths(3, 3))

#python #tree #recursion #dfs #neetcode

Tree: find all paths for a target sum DFS recursive with helper Python

class Tree(object):
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right 
 
tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))


def find_paths(root, required_sum):
    allPaths = []
  
    def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
      if currentNode is None:
        return
    
      # add the current node to the path
      currentPath.append(currentNode.val)
    
      # if the current node is a leaf and its value is equal to required_sum, save the current path
      if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
        allPaths.append(list(currentPath))
      else:
        # traverse the left sub-tree
        find_paths_recursive(currentNode.left, required_sum -
                             currentNode.val, currentPath, allPaths)
        # traverse the right sub-tree
        find_paths_recursive(currentNode.right, required_sum -
                             currentNode.val, currentPath, allPaths)
    
      # remove the current node from the path to backtrack,
      # we need to remove the current node while we are going up the recursive call stack.
      del currentPath[-1]
    
    find_paths_recursive(root, required_sum, [], allPaths)
    
    return allPaths

find_paths(tx, 5)

#python #tree #recursion #dfs #neetcode

Tree: is subtree of another tree DFS recursive with helper Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        #order of first two conditionals is important 
        if not subRoot: return True 
        if not root: return False 
        if self.sameTree(root, subRoot): return True 
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
        
        
    def sameTree(self, s, t): 
        if not s and not t: return True 
        if s and t and s.val == t.val: 
            return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right) 

        return False

#python #tree #recursion #dfs #neetcode

Binary Tree: are trees the same structurally and by value? DFS recursive without helper isSameTree Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True 
        if not p or not q: return False 
        if p.val != q.val: return False 
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

#javascript #object #deep #copy #clone #recursion

deep copy objects

function deepCopy(obj){
    let toString = Object.prototype.toString;
    if(typeof obj !== 'object') return obj;
    if(obj === null) return null;
    if(Array.isArray(obj)) return obj.map(deepCopy);
    let newObj = {};
    for(let key in obj){
        if(toString.call(obj[key])==='[object Date]'){
            newObj[key] = new Date(obj[key])
        } else if(toString.call(obj[key])==='[object RegExp]'){
            newObj[key] = new RegExp(obj[key])
        }else{
            newObj[key] = deepCopy(obj[key]);
        }
    }
    return newObj;
}

#javascript #fibonacci #recursion #algorithm

flatten array recursively

function flatten(arr) {
  let flat = []
  
  for(let prop of arr){
    if(Array.isArray(prop)){
      flat.push(...flattan(prop))
    } else {
      flat.push(prop)
    }
  }
  return flat
}

#javascript #fibonacci #recursion #algorithm

Count binary substring

function getSubstringCount(s) {
    // Write your code here
    let [current, prev, result] = [1, 0, 0]
    
    for(let i=1; i<s.length; i++){
        let left = s[i-1]
        let right = s[i]
        if(left == right){
            current++
        } else {
            prev = current
            current = 1
        }
        if(prev >= current){
            result++
        }
    }
    return result
}

#javascript #fibonacci #recursion #algorithm

fibonacci recursive solution

//find fibonacci numbers

function fib(n){
  if(n >=3 ){
    return fib(n-1) + fib(n-2)
  } else {
    return 1;
  }
}

console.log(fib(10))

#java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits

Possible Words From Phone Digits

class Solution
{
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
    {
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        Collections.sort(res); 
        return res;
                    
    }
    
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
    {
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            baseRes.add(""); 
  
            //returning a list containing empty string.
            return baseRes; 
        } 
        
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
  
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
      
        String code = hash[ch - '0']; 
  
        for (String val : prevRes) { 
  
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
            } 
        } 
        //returning the list.
        return Res; 
    }
}

#java #gfg #geeksforgeeks #recursion #powerset

Power Set Using Recursion

class LexSort
{
    static void solve(String s,String out, ArrayList<String> ans ,int i){
        if(i==s.length()){
            ans.add(out);
            return;
        }
        char ch=s.charAt(i);
        solve(s,out,ans,i+1);
        solve(s,out+String.valueOf(ch),ans,i+1);
    }
    
    //Function to return the lexicographically sorted power-set of the string.
    static ArrayList<String> powerSet(String s)
    {
        ArrayList<String> ans= new ArrayList<>();
        solve(s,"",ans,0);
        return ans;
    }
}

#java #gfg #geeksforgeeks #recursion #power #powerof numbers

Power Of Numbers

class Solution
{
    public long modfun(long n, long  R)
    {
        // Base cases 
        if (n == 0) 
            return 0; 
        // power zero mean answer is 1
        if (R == 0)  
            return 1; 
        // If R is even 
        long y; 
        if (R % 2 == 0) { 
            // finding r/2 power as power is even then storing answer in y and if power is even like 2^4 we can simply do (2^2)*(2^2)
            y = modfun(n, R/2);  
            y = (y * y) % 1000000007; 
        } 
      
        // If R is odd 
        else { 
            y = n % 1000000007; 
            // reduce the power by 1 to make it even. The reducing power by one can be done if we take one n out. Like 2^3 can be written as 2*(2^2)
            y = (y * modfun(n, R - 1) % 1000000007) % 1000000007; 
        } 
        // finally return the answer (y+mod)%mod = (y%mod+mod%mod)%mod = (y%mod)%mod
        return ((y + 1000000007) % 1000000007);  
        }
        
        
    long power(int N,int R)
    {
        return modfun(N,R)%1000000007;
        
    }

}

#java #gfg #geeksforgeeks #recursion #powerusing recursion #power

Power Using Recursion

class Solution
{
    static int RecursivePower(int n, int p)
    {
       if(p==0){
           return 1;
       }
       return n*RecursivePower(n, p-1);
    }
}

#java #gfg #geeksforgeeks #recursion #luckynumbers

Lucky Numbers

class Solution
{
    public static boolean check(int n,int counter)
    {
        if(counter<=n){
            if(n%counter==0)
                return false;
		    // calculate next position of input number
		    n=n-n/counter;
		    counter++;
		    // make recursive call with updated counter 
		    // and position return check(n, counter);
		    return check(n, counter);
        }    
       	else
       		return true;
    }
    
    // n: Input n
    // Return True if the given number is a lucky number else return False
    public static boolean isLucky(int n)
    {
        return check(n,2);
    }
}

#java #gfg #geeksforgeeks #recursion #digitalroot

Digital Root

class Solution
{
    public static int digitalRoot(int n)
    {
        if(n < 10)
            return n;

        return digitalRoot(n%10 + n/10);
    }
}

#java #gfg #geeksforgeeks #recursion #countdigits

Count Total Digits in a Number

class Solution
{
    public static int countDigits(int n)
    {
        if(n<10)
            return 1;
        else
            // recursively count the digits of n
            return 1+countDigits(n/10);
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #stringpermutations

Print all Permutations of A String

public class Permutation
{
	public static void main(String[] args)
	{
		String str = "ABC";
		int n = str.length();
		Permutation permutation = new Permutation();
		permutation.permute(str, 0, n-1);
	}

	/**
	* permutation function
	* @param str string to calculate permutation for
	* @param l starting index
	* @param r end index
	*/
	private void permute(String str, int l, int r)
	{
		if (l == r)
			System.out.println(str);
		else
		{
			for (int i = l; i <= r; i++)
			{
				str = swap(str,l,i);
				permute(str, l+1, r);
				str = swap(str,l,i);
			}
		}
	}

	/**
	* Swap Characters at position
	* @param a string value
	* @param i position 1
	* @param j position 2
	* @return swapped string
	*/
	public String swap(String a, int i, int j)
	{
		char[] arr = a.toCharArray();
		char temp = arr[i] ;
		arr[i] = arr[j];
		arr[j] = temp;
		return String.valueOf(arr);
	}

}

#java #gfg #geeksforgeeks #lecture #recursion #subsetsum

Subset Sum Problem (Recursive Solution)

// Naive recursive solution : Time Complexity : Θ(2^n)

import java.io.*;
import java.util.*;

class GFG {

	static int countSubsets(int arr[], int n, int sum)
	{
		if(n == 0)
			return sum==0 ? 1 : 0;

		return countSubsets(arr, n-1, sum) + countSubsets(arr, n-1, sum - arr[n-1]);
	}

	public static void main (String[] args) 
    {
		int n = 3, arr[]= {10, 20, 15}, sum = 25;

		System.out.println(countSubsets(arr, n, sum));
	}
}

#java #gfg #geeksforgeeks #lecture #recursion #josephusproblem

Josephus Problem

// Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int check(int n, int k)
    {
    	if(n == 1)
    		return 0;
    	else
    		return (check(n - 1, k) + k) % n;
    }

    static int josephus(int n, int k)
    {
    	return check(n, k) + 1;
    }
      
    public static void main(String args[]) 
    { 
        System.out.println(josephus(5, 3));  
    } 
}

#java #gfg #geeksforgeeks #lecture #recursion #towerofhanoi #toh

Tower of Hanoi

import java.util.*;
import java.io.*;

class GFG 
{ 
    static void ToH(int n, char A, char B, char C) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move 1 from " +  A + " to " + C); 
            return; 
        } 
        ToH(n-1, A, C, B); 
        System.out.println("Move " + n + " from " +  A + " to " + C); 
        ToH(n-1, B, A, C); 
    } 
   
    public static void main(String args[]) 
    { 
        int n = 2; 
        ToH(n, 'A', 'B', 'C');  
    } 
}

#java #gfg #geeksforgeeks #lecture #recursion #generate subsets

Generate all possible Subsets of given string

import java.io.*;
import java.util.*;

class GFG 
{
	static void printSub(String str, String curr, int index)
	{
		if(index == str.length())
		{
			System.out.print(curr+" ");
			return;
		}

		printSub(str, curr, index + 1);
		printSub(str, curr+str.charAt(index), index + 1);
	}
  
    public static void main(String [] args) 
    {
    	String str = "ABC";
    	
    	printSub(str, "", 0); 
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting

Rope Cutting Problem

import java.io.*;
import java.util.*;

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #digitssum

Sum of Digits Using Recursion

// Sum of Digits Using Recursion : Time Complexity : O(d), Space Complexity : O(d) 
// where d is the number of digits in number

import java.io.*;
import java.util.*;

class GFG 
{
	static int fun(int n)
	{
		if(n < 10)
			return n;

		return fun(n / 10) + n % 10;
	}
    public static void main(String [] args) 
    {
    	System.out.println(fun(253));
    }
}


// Iterative : Time Complexity : O(d), Space Complexity : O(1) {No Overhead & Less Aux. Space}

	static int getSum(int n)
	{
		int sum = 0;

		while (n != 0) {
			sum = sum + n % 10;
			n = n / 10;
		}

		return sum;
	}

#java #gfg #geeksforgeeks #lecture #recursion #palindrome

Palindrome Check using Recursion

// Time Complexity : O(n), Space Complexity : O(n)

import java.io.*;
import java.util.*;

class GFG 
{
	static boolean isPalindrome(String str, int start, int end)
	{
		if(start >= end)
			return true;

		return ((str.charAt(start)==str.charAt(end)) && 
			     isPalindrome(str, start + 1, end - 1));
	}
    public static void main(String [] args) 
    {
    	String s = "GeekskeeG";

    	System.out.println(isPalindrome(s, 0, s.length() -1));
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #naturalsum

Natural Number Sum using Recursion

// Time Complexity : O(n), Space Complexity : O(n)

import java.io.*;
import java.util.*;

class GFG 
{
	static int getSum(int n)
	{
		if(n == 0)
			return 0;

		return n + getSum(n - 1);
	}
    public static void main(String [] args) 
    {
    	int n = 4;
    	
    	System.out.println(getSum(n));
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #fibonacci #n-thfibonacci #fibonacciseries

Nth Fibonacci Series

// Time Complexity: O(2^n), Auxiliary Space: O(N).
// Fibonacci Series using Recursion

class fibonacci
{
	static int fib(int n)
	{
      // if (n == 0) return 0;
      // if (n == 1) return 1;
      if (n <= 1)
      	return n;
      
      return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
      int n = 9;
      System.out.println(fib(n));
	}
}

#java #gfg #geeksforgeeks #lecture #recursion #tailrecursion #tailcallelimination #factorial

Tail recursion and Tail call elimination - Factorial

// NON-TAIL RECURSIVE
 
import java.io.*;
import java.util.*;
 
class GFG 
{

	static void fun(int n)
	{
		if(n == 0 || n == 1)
			return 1;
 
		return n*fact(n - 1);
 
	}
  
    public static void main(String [] args) 
    {
    	fun(3);
    }

}




// TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG {

	
	static int fact(int n, int k)
	{
		if(n == 0 || n == 1)
			return k;

		return fact(n - 1, k * n);

	}
  
    public static void main(String [] args) 
    {
    	System.out.println(fact(3, 1));
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #tailrecursion #tailcall elimination

Tail recursion and Tail call elimination

// Example1 : NON-TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG 
{
  	// Print N to 1 Using Recursion
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.print(n+" ");

		fun(n - 1);

	}
    public static void main(String [] args) 
    {
    	fun(3);
    }
}

// Example2 : TAIL RECURSIVE

import java.io.*;
import java.util.*;

class GFG 
{
  	// Print 1 to N Using Recursion
	static void fun(int n, int k)
	{
		if(n == 0)
			return;

		System.out.print(k+" ");

		fun(n - 1, k + 1);

	}
    public static void main(String [] args) 
    {
    	fun(3, 1);
    }
}

#java #gfg #geeksforgeeks #lecture #recursion #print1ton using recursion

Print 1 to N Using Recursion

// Time Complexity : O(n), Space Complexity : O(n) (Recursive)

import java.io.*;
import java.util.*;

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		printToN(n - 1);

		System.out.print(n+" ");

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #printn to 1 using recursion

Print N to 1 Using Recursion

import java.io.*;
import java.util.*;

class GFG {

	
	static void printToN(int n)
	{
		if(n == 0)
			return;
		
		System.out.print(n+" ");
		
		printToN(n - 1);

	}
    public static void main(String [] args) 
    {
    	int n = 4;

    	printToN(n);
        
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #basecase #recursivefunction #binaryrepresentation

Recursion Output Practice - Part 2 (Binary Representation)

import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;
		
		fun(n / 2);

		System.out.println(n % 2);

	}
    public static void main(String [] args) 
    {
        fun(7);
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #basecase #recursivefunction #logn

Recursion Output Practice - Part 2 (logN with base 2)

class GFG {

	
	static int fun(int n)
	{
		if(n == 1)
			return 0;
		else
			return 1 + fun(n / 2);
	}
    public static void main(String [] args) 
    {
        System.out.println(fun(16));
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #basecase #recursivefunction

Recursion Output Practice - Part 1 (Example - 1)

import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		System.out.println(n);

		fun(n - 1);

		System.out.println(n);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #basecase #recursivefunction

Recursion Output Practice - Part 1 (Example - 2)

import java.io.*;
import java.util.*;

class GFG {

	
	static void fun(int n)
	{
		if(n == 0)
			return;

		fun(n - 1);

		System.out.println(n);
		
		fun(n - 1);
	}
    public static void main(String [] args) 
    {
        fun(3);
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #basecase #recursivefunction

Fun with Recursion - Introduction (Example - 2)

import java.io.*;
import java.util.*;

class GFG {

	
	static void fun1(int n)
	{
		if(n == 0)
			return;

		System.out.println("GFG");

		fun1(n - 1);
	}
    public static void main(String [] args) 
    {
        fun1(2);
    }

}

#java #gfg #geeksforgeeks #lecture #recursion #intro #methodcall #statementcall #methodinvoking

Fun with Recursion - Introduction (Example - 1)

import java.io.*;
import java.util.*;

class GFG {

	
	static void fun1()
	{
		System.out.println("fun1");
	}

	static void fun2()
	{
		System.out.println("Before fun1");

		fun1();

		System.out.println("After fun1");
	}

	public static void main (String[] args) {
		
		System.out.println("Before fun2");

		fun2();

		System.out.println("After fun2");

	}
}

#recursion #arrays

Recursion Array

import java.util.*;

public class Main {

  public static void main(String[] args) {
    // Write your code here

    int[] arr = {1,2,7,4,5};

    boolean ans = sorted(arr, 0);

    System.out.print(ans);

  }

  public static boolean sorted(int[] arr,int index) {
    if(index == arr.length-1){
      return true;
    }

    return arr[index]<arr[index+1] && sorted(arr, index+1);

  }
}

check if linked list is circular or not

code to reverse a linked list in the group of k

return the middle node in linked list and in the case of two node return the further one from head

reverse linked list using recrsion

reverse linked list using recursion

merge sort using recursion

code to check palindrome using recursion

rat in a maze problem

bubble sorting of the array using recursion.

power of function using recursion.

binary search using recursion

linear search using recursion.

check if array is sorted using recursion.

nth fibonacci number using recursion

Count no of Partitions of size at most m

Unique Paths

Tree: find all paths for a target sum DFS recursive with helper Python

Tree: is subtree of another tree DFS recursive with helper Python

Binary Tree: are trees the same structurally and by value? DFS recursive without helper isSameTree Python

deep copy objects

flatten array recursively

Count binary substring

fibonacci recursive solution

Possible Words From Phone Digits

Power Set Using Recursion

Power Of Numbers

Power Using Recursion

Lucky Numbers

Digital Root

Count Total Digits in a Number

Print all Permutations of A String

Subset Sum Problem (Recursive Solution)

Josephus Problem

Tower of Hanoi

Generate all possible Subsets of given string

Rope Cutting Problem

Sum of Digits Using Recursion

Palindrome Check using Recursion

Natural Number Sum using Recursion

Nth Fibonacci Series

Tail recursion and Tail call elimination - Factorial

Tail recursion and Tail call elimination

Print 1 to N Using Recursion

Print N to 1 Using Recursion

Recursion Output Practice - Part 2 (Binary Representation)

Recursion Output Practice - Part 2 (logN with base 2)

Recursion Output Practice - Part 1 (Example - 1)

Recursion Output Practice - Part 1 (Example - 2)

Fun with Recursion - Introduction (Example - 2)

Fun with Recursion - Introduction (Example - 1)

Recursion Array

Save snippets that work with our extensions