Hi guys because I'm still confused about recursion, I started challenging myself to solve recursive problem and I'm stuck in this problem.
description of the question:
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).


My solution is(function called Num_Way(String)) :
lets assume I've string "1234" so it's the same to say "1" + decode"234" or "12" +decode("34") so I must do recursively Num_Way, as a result: Num_Way("1234")=Num_Way("1")+Num_Way("234") or Num_Way("12")+Num_Way("34")
but the output is wrong if I write this, I should disregard from "1" and "12" (the digit that I split) and not considering them in the recursion calls...why?! I subproblem by one digit or two digit, if we didn't consider the one digit or two digit that we split the problem by then where did they gone?! and why we are not taking the Num_Way of them?

 

That basic problem is that you are mixing apples and oranges.

"1" + decode"234"

is nonsensical because "1" is not a number of ways to decode something, but decode"234" is. So you can't add them together.

Rephrase what you are trying to describe.

The number of ways to decode "1234" is equal to the sum of (the number of ways I can decode "234" after splitting of a leading "1") and (the number of ways I can decode "34" after splitting of a leading "12").

Now take those individually.

The number of ways that I can decode "234" after splitting of a leading "1" is simply the number of ways I can decode "234".

 

num of ways that I can decode "234" after splitting of a leading "1" is simply the number of ways I can decode "234".

My basic problem really why you're neglecting num of ways of what we are getting split by; i mean after split by "1" we are not consider it ..why? Maybe it's simple for others but really im founding a serious problem with that; when I say num of way of "1234" then it's includued also num of way of "1" and num of way of "234" why exactly the not leading element "1" after splitting act like nullity and we dont consider it? It's nonsense for me; actually I don't have the "good approach" to think why we don't need to consider the element that we cutted it from string? Here is my point ... If "1234" is the same as writing "1"+"234" then i should actually take into consideration the num of ways of "1"+ num of ways of "234" ..you see I got the idea of recursion but I need a lil boost/improve which why we dont consider the num of ways of what we have cutted from the string ..implicitly the non leading digit after splitting it from string it also related to the whole string before splitting...and for me really nonsense to just cut one digit and discard it...
why exactly we say the num of ways of "1234" is actually the num of ways "after spliting..." . the element that we have already split we disregard it ..why? Is it because we already know that's converted to letter from a-z? If so; then why is that leading me to discard it?! Knowing that i can solve it then mean i will neglect it...nonsense for me!!

To sum up; any good explanation may close this gap for me *neglecting the not leading element* ? Much appreciated ..if there's any analogous that describe a solution to pro lem with neglecting the non leading element of its input then much appreciated

 

My basic problem really why you're neglecting num of ways of what we are getting split by; i mean after split by "1" we are not consider it ..why? Maybe it's simple for others but really im founding a serious problem with that; when I say num of way of "1234" then it's includued also num of way of "1" and num of way of "234" why exactly the not leading element "1" after splitting act like nullity and we dont consider it? It's nonsense for me; actually I don't have the "good approach" to think why we don't need to consider the element that we cutted it from string? Here is my point ... If "1234" is the same as writing "1"+"234" then i should actually take into consideration the num of ways of "1"+ num of ways of "234" ..you see I got the idea of recursion but I need a lil boost/improve which why we dont consider the num of ways of what we have cutted from the string ..implicitly the non leading digit after splitting it from string it also related to the whole string before splitting...and for me really nonsense to just cut one digit and discard it...
why exactly we say the num of ways of "1234" is actually the num of ways "after spliting..." . the element that we have already split we disregard it ..why? Is it because we already know that's converted to letter from a-z? If so; then why is that leading me to discard it?! Knowing that i can solve it then mean i will neglect it...nonsense for me!!

To sum up; any good explanation may close this gap for me *neglecting the not leading element* ? Much appreciated ..if there's any analogous that describe a solution to pro lem with neglecting the non leading element of its input then much appreciated

Imagine you are counting the number of leaves on a tree and you want to do by recursively counting up the leaves on the branches. So you move up the three and run into where the tree forks into three branches. How do you count up the leaves? By adding the leaves on branch #1 to the leaves on branch #2 to the leaves on branch #3. Why don't you count the three branches as well?

Now, like many problems, the one you are proposing can be solved different ways. Another way is to walk the partition across the string and multiply the number of ways to split the left string by the number of ways to split the right string (i.e., you don't add them). You are essentially trying to mix the two methods.

 

Off the cuff without a lot of thought... Here's one way to do it (pseudo code):

main()
{
  string numbersString = "0123456789101112";
  int count = 0; 
  myFunc(numbersString, &count);
}

myFunc(string numbers, int *parseCounter)
{
  if(numbers.length >= 1)
  {
    parseCounter++;
    if(numbers.length >= 2 && first_two_digits_between_0_and_26)
    {
        parseCounter++;
    }
    numbers.delete_first_char();
    myFunc(numbers, parseCounter);
  }

}

 

Hi sir, I appreciate your effort for writing a pseudo code, but really I don't need to get it ready and just copy it like parrot, I already having my own code, and I just wanted to understand the idea of cutting the strings step by step in recursive way, anyway I appreciate your effort!

 

Imagine you are counting the number of leaves on a tree and you want to do by recursively counting up the leaves on the branches. So you move up the three and run into where the tree forks into three branches. How do you count up the leaves? By adding the leaves on branch #1 to the leaves on branch #2 to the leaves on branch #3. Why don't you count the three branches as well?

Now, like many problems, the one you are proposing can be solved different ways. Another way is to walk the partition across the string and multiply the number of ways to split the left string by the number of ways to split the right string (i.e., you don't add them). You are essentially trying to mix the two methods.

I would be lie if I say you're not helping me, You're superb ! thanks!!

 

Hi sir, I appreciate your effort for writing a pseudo code, but really I don't need to get it ready and just copy it like parrot, I already having my own code, and I just wanted to understand the idea of cutting the strings step by step in recursive way, anyway I appreciate your effort!

I appreciate your wanting to learn! My goal was really to show how recursion could work here. My method might have a bug, so it would be worth understanding what it does so you can determine if my method was correct, or if there is a logic error.

Also understand that recursion has limits. You can only call a function recursively so many times, and eventually all of the resources of the computer get used up and the program crashes, or fails nicely if you handle the failure in code.