Recursive program that accepts a non-negative integer as input and displays its vertically stacked digits

Question

I developed the recursive function vertical(), which accepts a non-negative integer as input and displays its vertically stacked digits.

For example:

>>> vertical(3124)
3
1
2
4

Solution:

def vertical(n):
    if n< 10:
        print(n)
    else:
        vertical(n//10)
        print(n%10)

n = 3124
vertical(n)

Could someone explain step by step how the above recursive solution works?

Answer 1

^{A tip to understand how any algorithm works is to do the table test. All right, for recursive algorithms it can be a little more confusing, but either way it’s worth a try.}

---

The basic idea of recursion is to solve the problem in a... recursive way, that is, you solve a smaller instance of the same problem, using the same algorithm (and if not tail recursion, you join the results later).

In your case, what would a recursive algorithm be like to show the digits of a stacked number? Basically, it would be something like this:

1. if the number only has one digit, just print the number itself and you’re done
2. if the number has more than one digit (let’s assume that the quantity is N digits):
   • 2.1. print the N - 1 first stacked digits
   • 2.2. print the last digit

Step 1 above corresponds to if n < 10 (with the detail that will not work very well with negative numbers, and the function could even check this case and give an error, for example, but anyway). This is the basic case, in which no recursive call is required.

Step 2 corresponds to else, when the number has more than one digit and we need the recursive call.

But how to solve step 2.1? Simple, you run the same algorithm, but instead of considering all the digits, you consider only the first N - 1 (ie, you call the same function recursively, passing a number that only has the N - 1 first digits, and after it returns, you perform step 2.2).

In the case of number 3124, it would look like this:

• 3124 is less than 10? No, get into the else, what call vertical(3124 // 10), that is to say, vertical(312) (the operator // is the entire division, i.e., ignoring the decimals of the result). This is step 2.1, I called the function recursively, passing only the N - 1 first digits.
  • now we are inside the call vertical(312):
  • 312 is less than 10? No, get into the else, what call vertical(312 // 10), that is to say, vertical(31) - again, it is step 2.1
    • now we are inside the call vertical(31):
    • 31 is less than 10? No, get into the else, what call vertical(31 // 10), that is to say, vertical(3) - once again we execute step 2.1
      • now we are inside the call vertical(3):
      • 3 is less than 10? Yes, print 3 and the function terminates its execution (i.e., the call vertical(3) has nothing more to do and ends)
    • we’re still inside the call vertical(31), and now we can execute step 2.2, which is to print the value of 31 % 10 - the rest of the division 31 per 10, i.e., 1.
  • we’re still inside the call vertical(312), and now we can execute step 2.2, which is to print the value of 312 % 10, that is to say, 2
• we’re still inside the call vertical(3124), and now we can execute step 2.2, which is to print the value of 3124 % 10, that is to say, 4

Thus, the algorithm prints 3, 1, 2 and 4, in this order. What can confuse is the fact that with each recursive call the context changes: the number being analyzed is another, although the algorithm is the same.

Another detail is that with each call that enters the else, Step 2.2 needs to wait for step 2.1 to finish. But since step 2.1 is the recursive call, it can call step 2.1 again, which makes another recursive call (and needs to wait for it to return to perform its own step 2.2) and so on.

Answer 2

The idea of recursion sub-divide the problem into problems smaller so it can be solved

 def vertical(n):
    if n < 10:
        print(n)
    else:
        vertical(n//10) # // divisão inteira 
        print(n%10) # modulo da divisão


# entrada

n = 3124
vertical(n) # n = 3124
vertical(n) # n = 312
vertical(n) # n = 31
vertical(n) # n = 3

running algorithm will run all recursions passing entire division until it falls in case base that would n < 10 and will settle down up you may think he puts in a stack and then remove from the stack getting the result vertically to get the results he will remove module from the division in print

3 
1 
2 
4