Recursion COPY Flashcards
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
}
}
3
2
1
1
2
3
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
} }
1
2
1
3
1
2
1
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));
}
}
}
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.
include using namespace std;
void fun(int n)
{
if(n == 0)
return;
fun(n / 2);
cout\<}
int main() {
fun(7);
return 0;
}
1
1
1
It shows the binary representation of the input number
print numbers from N to 1 using recursion.
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;
}
print numbers from 1 to N using recursion
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;
}
Write a program to calculate factorial with recursion
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;
}
Write a program to calculate fibonacci numbers with recursion
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;
}
find sum of first n natural numbers.
#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;
}
a recursive function to check if a string is palindrome or not
#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;
}
Sum of Digits Using Recursion
#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;
}
Rope Cutting Problem:
#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;
}
Generate Subsets
#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
Tower of Hanoi
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:
- Only one disk can be moved at a time.
- 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.
- 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
Print 1 to N without Loop
class Solution
{
public void printNos(int N)
{
if (N<1)
return;
printNos(N-1);
System.out.print(N+” “);
}
}
Count Total Digits in a Number using recursion
// { 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
Sum of digits of a number using recursion
int sumOfDigits(int n)
{
if (n==0)
return 0;
return sumOfDigits(n/10) + (n%10);
}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
int theSequence(int N)
{
if (N==0)
return 1;
return N + N\*(theSequence(N-1));
}find nCr using recursion
int nCr(int n,int r)
{
if (r==0 or r==n)
return 1;
return nCr(n-1,r-1) +nCr(n-1,r);
}Check palindrome using recursion
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);
}
};
Calculate GCD with recursion
int GCD(int a,int b)
{
if (b != 0)
return GCD(b, a % b);
else
return a;
}
};Print all the elements in an array using recursion
void printArrayRecursively(int arr[],int n)
{
if (n==0)
return;
printArrayRecursively(arr, n-1);
cout (( arr[n-1] (( " ";
return;
}Power Using Recursion
int RecursivePower(int n, int p)
{
if (p==0)
return 1;
if (p==1)
return n;
return n\*RecursivePower(n, p-1);
}Program to calculate product of digits of a number
//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; }
Disadvantage of Recursion:
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.
Advantages of Recursion
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.
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.
// 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); }
What is Tail Recursion:
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.
void printN(int N)
{
if(N==0)
return;
else
cout((N((“ “;
printN(N-1);
}
Which one is Better-Tail Recursive or Non Tail-Recursive?
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.
Can a non-tail recursive function be written as tail-recursive to optimize it?
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); }
Josephus problem
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;
}
String permutations
// 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;
}
