This paper presents a new technique for recognizing Arabic spoken digits, either isolated or connected. In this technique , a heuristic guided search function is defined based on both of the probability of occurrence of each phoneme within the digit, as well as the knowledge of the possible position that can be occupied by the phoneme. This technique when applied on the isolated input digits gives an accuracy of 100%. A recommended-shift heuristic technique is then adopted to allow for fast and correct recognition of the connected Arabic digits. In the recommendation heuristic, each digit tries to align the input stream of phonemes to achieve a best local probability function, and leaves a request of the amount of shift. These local shift requests are then analyzed globally to determine the best. The resultant recognizer system is independent on the number of input connected digits. No backtracking is required, which enhances the speed of the recognizer. The proposed recognizer gives an accuracy of 98.3% for the connected Arabic digits