Recursive Implementation of atoi()
The atoi() function takes a string (which represents an integer) as an argument and returns its value. We have discussed iterative implementation of atoi(). How to compute recursively?
Approach:
The idea is to separate the last digit, recursively compute the result for the remaining n-1 digits, multiply the result by 10 and add the obtained value to the last digit.
Below is the implementation of the idea.
C++
// Recursive C program to compute atoi() #include <cctype> #include <cstring> #include <iostream> using namespace std; // Recursive function to compute atoi() int myAtoiRecursive( char * str, int n) { // If str is NULL or str contains non-numeric // characters then return 0 as the number is not // valid int count = 0, check; // loop to count the no. of alphabets in str for ( int i = 0; i <= strlen (str); ++i) { // check if str[i] is an alphabet check = isalpha (str[i]); // increment count if str[i] is an alphabet if (check) ++count; } if (count != 0) { return 0; } // Base case (Only one digit) if (n == 1) return *str - '0' ; // If more than 1 digits, recur for (n-1), multiply // result with 10 and add last digit return (10 * myAtoiRecursive(str, n - 1) + str[n - 1] - '0' ); } // Driver Program int main( void ) { char str[] = "112" ; int n = strlen (str); printf ( "%d" , myAtoiRecursive(str, n)); return 0; } |
Java
// Recursive Java program to compute atoi() class GFG{ // Recursive function to compute atoi() static int myAtoiRecursive(String str, int n) { // If str is NULL or str contains non-numeric // characters then return 0 as the number is not // valid if (str == "" || !str.matches( "^\\d*$" )) { return 0 ; } // Base case (Only one digit) if (n == 1 ) { return str.charAt( 0 ) - '0' ; } // If more than 1 digits, recur for (n-1), // multiply result with 10 and add last digit return ( 10 * myAtoiRecursive(str, n - 1 ) + str.charAt(n - 1 ) - '0' ); } // Driver code public static void main(String[] s) { String str = "112" ; int n = str.length(); System.out.println(myAtoiRecursive(str, n)); } } |
Python3
# Python3 program to compute atoi() # Recursive function to compute atoi() def myAtoiRecursive(string, num): # If str is NULL or str contains non-numeric # characters then return 0 as the number is not # valid if string.isalpha() : return 0 ; if ( len (string) = = 0 ): return 0 ; # base case, we've hit the end of the string, # we just return the last value if len (string) = = 1 : return int (string) + (num * 10 ) # add the next string item into our num value num = int (string[ 0 : 1 ]) + (num * 10 ) # recurse through the rest of the string # and add each letter to num return myAtoiRecursive(string[ 1 :], num) # Driver Code string = "112" print (myAtoiRecursive(string, 0 )) |
C#
// Recursive C# program to compute atoi() using System; using System.Text.RegularExpressions; class GFG{ // Recursive function to compute atoi() static int myAtoiRecursive( string str, int n) { // If str is NULL or str contains non-numeric // characters then return 0 as the number is not // valid if (Regex.IsMatch(str, "^[a-zA-Z]*$" )){ return 0; } // Base case (Only one digit) if (n == 1) { return str[0] - '0' ; } // If more than 1 digits, recur for (n-1), // multiply result with 10 and add last digit return (10 * myAtoiRecursive(str, n - 1) + str[n - 1] - '0' ); } // Driver code public static void Main() { string str = "112" ; int n = str.Length; Console.Write(myAtoiRecursive(str, n)); } } |
Javascript
<script> // Recursive Javascript program to compute atoi() // Recursive function to compute atoi() function myAtoiRecursive(str, n) { // If str is NULL or str contains non-numeric // characters then return 0 as the number is not // valid if (str.match(/^[A-Za-z]+$/)) { return 0; } // Base case (Only one digit) if (n == 1) { return str[0].charCodeAt() - '0' .charCodeAt(); } // If more than 1 digits, recur for (n-1), // multiply result with 10 and add last digit return (10 * myAtoiRecursive(str, n - 1) + str[n - 1].charCodeAt() - '0' .charCodeAt()); } let str = "112" ; let n = str.length; document.write(myAtoiRecursive(str, n)); </script> |
Output
112
Time complexity: O(n),
Auxiliary Space: O(n)