Module: (Python) Subroutines. recursion


Problem

5/12

Recursion and iteration

Theory Click to read/hide

Recursion and iteration
To understand recursion, you need to understand recursion...
 
Iteration in programming - one stepof a cyclic data processing process. 
Often iterative algorithms at the current step (iteration) use the result of the same operation or action calculated at previous steps.  One example of such calculations is the calculation of recurrence relations. 
A simple example of a recursive value is the factorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
The calculation of the value at each step (iteration) is \(N=N \cdot i\) .  When calculating the value of \(N\), we take the already stored value \(N\).< br />
The factorial of a number can also be described using the recurrent formula:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

You may notice that this description is nothing more than a recursive function.
Here the first line (\(n <= 1\)) is the base case (recursion termination condition) and the second line is the transition to the next step. 
Recursive factorial function Iterative algorithm
def Factorial(n): if n > 1: return n * Factorial(n - 1) else:   return 1 x=1 for i in range(1, n + 1): x = x * i;

It should be understood that function calls involve some additional overhead, so a non-recursive factorial calculation will be slightly faster. 

Conclusion: where you can write a program with a simple iterative algorithm, without recursion, then you need to write without recursion. But still, there is a large class of problems where the computational process is implemented only by recursion.
On the other hand, recursive algorithms are often more understandable.
 

Problem

Define a function K(n) that returns the number of digits in a given natural number n as

\(\begin{equation*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{cases} \end{equation*}\).

Write a recursive function to calculate the number of digits in a natural number n using the ratio above.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def CountDigit(n):      
        return 1 + CountDigit(n//10)
        
n = int(input())
print(CountDigit(n))

     

Program check result

To check the solution of the problem, you need to register or log in!