First Capital Using Recursion

Last Updated on March 23, 2022 by Ria Pathak

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given a String T, find the 1st occurrence of the capital (uppercase) alphabet. Print its index if present, else -1.

See original problem statement here

For Example:

Input : T = prepBytes

Output : 4

Input : T = helloWorld

Output : 5

Can we use Recursion here ?

Yes, the problem can be divided into sub problems, for example T = "prepBytes",
check if first character is Upper Case. If Yes print index else search in the remaining string.

SOLVING APPROACH:

1. Create a function with three parameters a string, start index, end index.

2. Base conditions form the Backbone of recursion, so if start becomes greater than end, simply return -1.

3. Because this implies entire string has been traversed but no upper case letter was found.

4. If the Ascii value of current char is greater than or equal to 65 and less than or equal to 90, this means an upper case letter is found, simply return this index value.

AlGORITHM:

IsUpperCase(string, i, j)

  if (entire string is traversed or i becomes greater than j)
    return -1

  if (character at ith index is upper case)
    return i
  else
    return IsUpperCase(string, i+1, j)

SOLUTIONS:

#include <stdio.h>

int first_upper(char s[],int i){
  if(s[i] == '\0')                   //base condition
    return -1;
  if(s[i] >= 65 && s[i] <=90)
    return i;
  else
    return first_upper(s,i+1);
}
int main()
{
  int n;
  scanf("%d",&n);
  while(n--){
    char s[100000];
    scanf("%s",s);
    printf("%d\n",first_upper(s,0));

  }
  return 0; 
}

#include <bits/stdc++.h>
using namespace std;

int first_upper(string s,int first,int last){

  if(first>last)       //base condition
    return -1;
  if(s[first] >= 65 && s[first] <= 90)
    return first;
  else
    return first_upper(s,first+1,last);
}
int main()
{
  int n;cin>>n;
  while(n--){
    string s;cin>>s;
    int first = 0;
    int last = s.size()-1;
    cout<<first_upper(s,first,last)<<"\n";
  }
  return 0;
}

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

public class Main {

  static int first_upper(String s,int first){
  if(first >= s.length())          //base condition
    return -1;
  if (Character.isUpperCase(s.charAt(first)))  
      return first;
  else
    return first_upper(s,first+1);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(n!=0){
      String s = sc.next();
      int first = 0;
      System.out.println(first_upper(s,first));
      n--;
    }
  }
}

def first_upper(s, first, last):
	
	if(first > last):
		return -1
	
	if(ord(s[first]) >= 65 and ord(s[first]) <= 90):
		return first

	else:
		return first_upper(s,first+1,last)

for _ in range(int(input())):

	s = input()
	first = 0
	last = len(s) - 1

	print(first_upper(s, first, last))

[forminator_quiz id="618"]

This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.