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; }
