Recursion COPY

Question 1

public class Main {
    // Recursive function
    static void fun(int n) {
        if (n == 0)
            return;

        System.out.print(n + " "); // Print n before recursion

        fun(n - 1); // Recursive call

        System.out.print(n + " "); // Print n after recursion
    }

    public static void main(String[] args) {
        fun(3); // Call the function with n = 3
    }
}

Answer 1

3
2
1
1
2
3

Question 2

public class RecursionExample {

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

    fun(n - 1);
    System.out.print(n + " "); // Printing similar to C++'s cout
    fun(n - 1);
}

public static void main(String[] args) {
    fun(3); // Start recursion with 3
} }

Answer 2

1
2
1
3
1
2
1

Question 3

public class RecursiveCount {
    /**
     * Recursive function that calculates how many times n can be divided by 2
     * 
     * @param n The input number
     * @return Number of times n can be divided by 2 until reaching 1
     */
    public static int fun(int n) {
        // Base case: when n becomes 1, stop recursion
        if (n == 1) {
            return 0;
        } 
        // Recursive case: divide n by 2 and add 1 to the count
        else {
            return 1 + fun(n / 2);
        }
    }

    /**
     * Main method to demonstrate the recursive function
     */
    public static void main(String[] args) {
        // Test the function with different input values
        int[] testValues = {16, 18, 32, 10};
        
        for (int value : testValues) {
            System.out.println("Input: " + value + ", Result: " + fun(value));
        }
    }
}

Answer 3

It shows the log value of n. eg- for fun(16) the answer would be 4.

Let me break down this intriguing recursive function and explain its purpose and behavior in depth:

Conceptual Understanding
The function fun(int n) is designed to count how many times you can divide a number by 2 before reaching 1. It’s essentially tracking the number of integer divisions needed to reduce the input to 1.

Recursive Mechanism
1. Base Case: When n becomes 1, the function returns 0. This is the stopping condition for the recursion.
2. Recursive Case: For any number larger than 1, the function does two things:
- Divides the number by 2 (integer division)
- Adds 1 to the recursive call’s result

Step-by-Step Example
Let’s trace what happens when we call fun(16):
- First call: fun(16)
- 16 ÷ 2 = 8
- Returns 1 + fun(8)
- Second call: fun(8)
- 8 ÷ 2 = 4
- Returns 1 + fun(4)
- Third call: fun(4)
- 4 ÷ 2 = 2
- Returns 1 + fun(2)
- Fourth call: fun(2)
- 2 ÷ 2 = 1
- Returns 1 + fun(1)
- Final call: fun(1)
- Returns 0

So fun(16) would return 4, because 16 can be divided by 2 four times before reaching 1.

Key Observations
- This is essentially calculating the floor of log base 2 of the input number
- It works only with positive integers
- Uses integer division (so 5 ÷ 2 would become 2)
- The recursion stops when the number becomes 1

Mathematical Insight
The function is mathematically equivalent to finding how many times you can halve a number before it becomes 1. This is closely related to the concept of logarithms.

Question 4

include using namespace std;

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

fun(n / 2);

cout\<}
int main() {

fun(7);

return 0;
}

Answer 4

1

1

1

It shows the binary representation of the input number

Question 5

print numbers from N to 1 using recursion.

Answer 5

include using namespace std;

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

cout<
printToN(n - 1);

}

int main() {

int n = 4;

printToN(n);

return 0;
}

Question 6

print numbers from 1 to N using recursion

Answer 6

include

using namespace std;

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

printToN(n - 1);

cout<

}

int main() {

int n = 4;

printToN(n);

return 0;
}

Question 7

Write a program to calculate factorial with recursion

Answer 7

include stdio.h

int fact(int n)
{
 if(n==0)
 return 1;

return n*fact(n-1);
}

int main() 
{
 printf("Enter the value of N \n");
 int n;
 scanf("%d",&n);
 printf("%d\n",fact(n));

return 0;
}

Question 8

Write a program to calculate fibonacci numbers with recursion

Answer 8

include stdio.h

int fib(int n)
{
 if(n\<=1)
 return n;

 return fib(n-1)+fib(n-2);
}

int main() 
{
 printf("Enter the value of N \n");
 int n;
 scanf("%d",&n);
 printf("%d\n",fib(n));

return 0;
}

Question 9

find sum of first n natural numbers.

Answer 9

#include iostream
using namespace std;

int getSum(int n)
{
if(n == 0)
 return 0;

return n + getSum(n - 1);

}

int main() {

int n = 4;

cout<
return 0;
}

Question 10

a recursive function to check if a string is palindrome or not

Answer 10

#include iostream
using namespace std;

bool isPalindrome(string str, int start, int end)
{
if(start \>= end)
 return true;

return ((str[start]==str[end]) &&
isPalindrome(str, start + 1, end - 1));
}

int main() {

string s = “GeekskeeG”;

printf(“%s”, isPalindrome(s, 0, s.length() -1) ? “true” : “false”);

return 0;
}

Question 11

Sum of Digits Using Recursion

Answer 11

#include iostream
using namespace std;

int fun(int n)
{
if(n \< 10)
 return n;

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

int main() {

cout
return 0;
}

Question 12

Rope Cutting Problem:

Answer 12

#include iostream
using namespace std;

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

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

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

return res + 1; 
}
int main() {

int n = 5, a = 2, b = 1, c = 5;

cout maxCuts(n, a, b, c);

return 0;
}

Question 13

Generate Subsets

Answer 13

#include (iostream\>
using namespace std;

void printSub(string str, string curr, int index)
{
if(index == str.length())
{
cout((curr((“ “;
return;
}

printSub(str, curr, index + 1);
printSub(str, curr+str[index], index + 1);
}

int main() {

string str = “ABC”;

printSub(str, “”, 0);

return 0;
}

Output;

C B BC A AC AB ABC

Question 14

Tower of Hanoi

Answer 14

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk

// C++ recursive function to 
// solve tower of hanoi puzzle 
#include (bits/stdc++.h\>
using namespace std;

void towerOfHanoi(int n, char from_rod,
char to_rod, char aux_rod)
{
if (n == 0)
{
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
cout (( “Move disk “ (( n (( “ from rod “ (( from_rod ((
“ to rod “ (( to_rod (( endl;
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

// Driver code
int main() 
{ 
 int n = 4; // Number of disks 
 towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods 
 return 0; 
}

Output
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C

Question 15

Print 1 to N without Loop

Answer 15

class Solution
{

public void printNos(int N)
{
if (N<1)
return;
printNos(N-1);
System.out.print(N+” “);
}
}

Question 16

Count Total Digits in a Number using recursion

Answer 16

// { Driver Code Starts
//Initial Template for C++

#include (iostream\>
using namespace std;

// } Driver Code Ends
//User function Template for C++

class Solution{
 public:
 //Complete this function
 int countDigits(int n)
 {
 if (n/10 == 0)
 return 1;
 return (1 + countDigits(n/10));
 }
};

// { Driver Code Starts.

int main() {
int T;

//taking testcases
cin>>T;
while(T–)
{
int n;

 //taking number n
 cin\>\>n;

//calling countDigits
Solution obj;
cout((obj.countDigits(n)((endl;

}
return 0;
}

// } Driver Code Ends

Question 17

Sum of digits of a number using recursion

Answer 17

int sumOfDigits(int n)
{
 if (n==0)
 return 0;
 return sumOfDigits(n/10) + (n%10);
}

Question 18

You are given a number n. You need to recursively find the nth term of the series S that is given by:
S(n) = n+ n*(S(n-1)) and S(0) = 1

Example 1:

Input:n = 2Output: 6

Example 2:

Input:n = 3Output: 21

Answer 18

int theSequence(int N)
{
 if (N==0)
 return 1;
 return N + N\*(theSequence(N-1));
}

Question 19

find nCr using recursion

Answer 19

int nCr(int n,int r)
{
 if (r==0 or r==n)
 return 1;
 return nCr(n-1,r-1) +nCr(n-1,r);
}

Question 20

Check palindrome using recursion

Answer 20

class Solution{
 public:
 bool helper(string n, int start, int end){
 if (start\>=end)
 return 1;
 return (n[start]==n[end]) and helper(n, start+1, end-1);
 }
 bool isPalin(int N)
 {
 string n = to\_string(N);
 int start=0;
 int end = n.length()-1;
 return helper(n, start, end);

}
};

Question 21

Calculate GCD with recursion

Answer 21

int GCD(int a,int b)
 {
 if (b != 0)
 return GCD(b, a % b);
 else
 return a;
 }
};

Question 22

Print all the elements in an array using recursion

Answer 22

void printArrayRecursively(int arr[],int n)
 {
 if (n==0)
 return;
 printArrayRecursively(arr, n-1);
 cout (( arr[n-1] (( " ";
 return;
 }

Question 23

Power Using Recursion

Answer 23

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

Question 24

Program to calculate product of digits of a number

Answer 24

//Recursive function to get product of the digits

#include (iostream\>
using namespace std;

int getProduct(int n){
// Base Case
if(n == 0){
 return 1 ;
}

// get the last digit and multiply it with remaining digits
return (n%10) \* getProduct(n/10) ;
}

int main() {

// call the function
cout((getProduct(125) ;
return 0;
}

Question 25

**Disadvantage of Recursion**:

Answer 25

Note that both recursive and iterative programs have the same problem-solving powers, i.e., every recursive program can be written iteratively and vice versa. Recursive program has greater space requirements than iterative program as all functions will remain in the stack until the base case is reached. A recursive program also has greater time requirements because of function calls and return overhead.

Question 26

**Advantages of Recursion**

Answer 26

Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. For such problems, it is preferred to write recursive code. We can write such codes also iteratively with the help of the stack data structure.

Question 27

Given an unsorted array of **N** elements and an element **X**. The task is to write a recursive function to check whether the element X is present in the given array or not.

Answer 27

``` // arr[] is the given array // l is the lower bound in the array // r is the upper bound // x is the element to be searched for // l and r defines that search will be // performed between indices l to r ``` bool recursiveSearch(int arr[], int l, int r, int x) { if (r ( l) return false; if (arr[l] == x) return true; if (arr[r] == x) return true; ``` return recursiveSearch(arr, l + 1, r - 1, x); } ```

Question 28

**What is Tail Recursion**:

Answer 28

A recursive function is said to be following Tail Recursion if it invokes itself at the end of the function. That is, if all of the statements are executed before the function invokes itself then it is said to be following Tail Recursion. ## Footnote void printN(int N) { if(N==0) return; else cout((N((" "; printN(N-1); }

Question 29

**Which one is Better-Tail Recursive or Non Tail-Recursive?**

Answer 29

The tail-recursive functions are considered better than non-tail recursive functions as tail-recursion can be optimized by the compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.

Question 30

**Can a non-tail recursive function be written as tail-recursive to optimize it?**

Answer 30

Consider the following function to calculate factorial of N. Although it looks like Tail Recursive at first look, it is a non-tail-recursive function. If we take a closer look, we can see that the value returned by fact(N-1) is used in fact(N), so the call to fact(N-1) is not the last thing done by fact(N). ``` int fact(int N) { if (N == 0) return 1; ``` return N\*fact(N-1); } ``` The above function can be written as a Tail Recursive function. The idea is to use one more argument and accumulate the factorial value in the second argument. When N reaches 0, return the accumulated value. int factTR(int N, int a) { if (N == 0) return a; ``` ``` return factTR(N-1, N\*a); } ```

Question 31

Josephus problem

Answer 31

#include (stdio.h\> int josephus(int n, int k) { if (n == 1) return 1; else /\* The position returned by josephus(n - 1, k) is adjusted because the recursive call josephus(n - 1, k) considers the original position k%n + 1 as position 1 \*/ return (josephus(n - 1, k) + k-1) % n + 1; } ``` // Driver Program to test above function int main() { int n = 14; int k = 2; printf("The chosen place is %d", josephus(n, k)); return 0; } ```

Question 32

String permutations

Answer 32

``` // C++ program to print all // permutations with duplicates allowed #include (bits/stdc++.h\> using namespace std; ``` ``` // Function to print permutations of string // This function takes three parameters: // 1. String // 2. Starting index of the string // 3. Ending index of the string. void permute(string a, int l, int r) { // Base case if (l == r) cout((a((endl; else { // Permutations made for (int i = l; i (= r; i++) { ``` ``` // Swapping done swap(a[l], a[i]); ``` ``` // Recursion called permute(a, l+1, r); ``` ``` //backtrack swap(a[l], a[i]); } } } ``` ``` // Driver Code int main() { string str = "ABC"; int n = str.size(); permute(str, 0, n-1); return 0; } ```