Recursion Assignment
1. Fibonacci Number
You are given a non-negative integer n. Your task is to compute the n-th Fibonacci
number using a recursive approach. The Fibonacci sequence is defined as follows:
F(0) = 0
F(1) = 1
For any n > 1: F(n) = F(n - 1) + F(n - 2)
You must implement a recursive solution that computes and returns the n-th Fibonacci
number.
Input Format
A single integer n the position in the Fibonacci sequence.
Output Format
A single integer the value of the n-th Fibonacci number.
Sample Input 1
Sample Output 1
Explanation
F(4) = F(3) + F(2) = 2 + 1 = 3
Sample Input 2
6
Sample Output 2
Explanation
F(6) = F(5) + F(4) = 5 + 3 = 8
Constraints
0 ≤ n ≤ 30
class Solution {
public int fib(int n) {
//Write your code here
}
}
2. Last Number Standing
You are given an integer n, representing a list of integers from 1 to n, sorted in
increasing order.
Perform the following elimination process until only one number remains:
Remove the first element and every second element from left to right.
Then from right to left, remove the last and every second element.
Repeat the above two steps alternately (left-to-right, then right-to-left), continually
removing every second remaining element.
Your task is to return the last number that remains in the list.
Input Format:
A single integer n.
Output Format:
A single integer the last remaining number after elimination.
Sample Input 1:
Sample Output 1:
Explanation:
List = [1, 2, 3, 4, 5, 6, 7, 8, 9] → [2, 4, 6, 8] → [2, 6] → [6]
Sample Input 2:
Sample Output 2:
Constraints:
1 ≤ n ≤ 10^6
class Solution {
public int lastRemaining(int n) {
//Write your code here
}
}
3. Last Index of x
Given an array of integers of length N and a target integer x, your task is to find the last
index at which x appears in the array. If x is not found, return -1.
You must solve this recursively, and the array should be traversed from index 0 (not
from the end).
Input Format
The first line contains a single integer N the size of the array.
The second line contains N space-separated integers the array elements.
The third line contains a single integer x the target element to find.
Output Format
A single integer — the last index of x in the array (or -1 if not found).
Sample Input 1
4
9 8 10 8
8
Sample Output 1
Sample Input 2
5
1 2 3 2 5
2
Sample Output 2
Constraints
1 ≤ N ≤ 10³
Array values may be positive or negative.
Indexing starts from 0.
class Solution {
public int lastIndex(int[] arr, int x) {
//Write your code here
}
}
4. AB Pattern String
You are given a string S consisting only of characters 'a' and 'b'. You need to
determine recursively whether the string follows these specific pattern rules:
The string must begin with the character 'a'.
Each 'a' must be followed by either:
nothing,
another 'a', or
the substring "bb".
Each "bb" must be followed by either:
nothing, or
an 'a'.
Return true if the string satisfies the above rules, else return false.
Input Format:
A single string S.
Output Format:
Return "true" or "false" (in lowercase).
Sample Input 1:
abb
Sample Output 1:
true
Explanation: The string starts with 'a', and it is followed by "bb" which is allowed. "bb"
is at the end, so no violation. Hence, the answer is true.
Sample Input 2:
abababa
Sample Output 2:
false
Explanation: After the first 'a', a single 'b' appears, which violates the rule that 'a'
must be followed by nothing, another 'a', or "bb". Hence, the answer is false.
Constraints:
1 ≤ |S| ≤ 1000
S contains only lowercase letters 'a' and 'b'.
class Solution {
public boolean isValid(String s) {
//Write your code here
}
}
5. Tower of Hanoi — Count Moves
You are given n disks placed on rod 1, arranged in ascending order from bottom to top
(i.e., the smallest disk is at the top). The goal is to move all the disks from rod 1 to rod 3
using rod 2 as an auxiliary rod. However, the movement of disks must follow two rules:
Only one disk can be moved at a time.
A disk can only be placed on top of a larger disk or an empty rod.
Your task is to determine the minimum number of steps required to transfer all the disks
from rod 1 to rod 3 following the above rules.
Input Format:
n is the number of disks
Output Format:
Return a single integer — the minimum number of steps required to complete the
transfer.
Sample Input 1:
Sample Output 1:
Explanation:
For n = 2, the steps will be:
Move disk 1 from rod 1 to rod 2
Move disk 2 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 3 Total steps = 3
Sample Input 2:
Sample Output 2:
Explanation:
For n = 3, the steps will be:
Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 3 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3 Total steps = 7
Constraints:
0 ≤ n ≤ 12
class Solution {
public long countMoves(int n) {
//Write your code here
}
}