Must-Try Recursion Problem Sets for Programmers

In the previous blog, I taught recursion. In this blog, I will solve some recursion problems. If you are new, I strongly recommend you read the blog on recursion Recursion Blog (link to the blog)

Question 1: Sum of Digits

How to find the sum of digits of a positive integer number using recursion?

Step 1: Recursive case - the flow

Let's look at some digits -

10 10/10 = 1 and remainder 0

54 54/10 = 5 and remainder 4

112 112/10 = 11 and remainder 2

11/10 = 1 and remainder 1

So, the case is f(n) = n%10 + f(n//10)

def sum(n): 
    return int(n%10) + sum(int(n//10))
sum(4) #it will through error

Step 2: Base case - the stopping criterion

Here, if we put n=0, sum of zero is zero. So we can use this as our base case.

def sum(n): 
    if n = 0: 
        return 0
    else: 
        return int(n%10) + sum(int(n//10))
sum(12)

Step 3: Unintentional case - the constraint

The number must be positive and it should be integer. Otherwise, the code will crash. So, let's put the unintentional case and complete the code

def sum(n): 
    assert n >= 0 and int(n) == n, "The number has to be a positive integer"
    if n = 0: 
        return 0
    else: 
        return int(n%10) + sum(int(n//10))
sum(12)
sum(-112) 
sum(3.4) 
sum(73)

Done.

Question 2: Power

How to calculate power of a number using recursion?

Let's say x raised to the power of n. It can be written like this : x^n = x*x*x*..(n times)...*x (we are multiplying x with itself n times)

Step 1: Recursive case - the flow

2^4 = 2*2*2*2 (we are summing up the exponents together). From exponent formula, (x^a * x^b = x^a+b) we can add the exponents if they have the same base. So taking this rule from math, we can write the equation like this : x^n = x * x^n-1 (our recursive case)

Step 2: Base case - the stopping criterion

Any given number raised to be power of zero, is going to be one. This is our base case

Step 3: Unintentional case - the constraint

To escape from getting into infinity loop.

def power(base, exp): 
    assert int(exp) == exp, "the exponent must be integer only"
    if exp == 0: 
        return 1
    elif exp < 0: 
        return 1/base * power(base, exp+1) 
    else: 
        return base * power(base, exp-1) 

print(power(1,4) #running
print(power(-1,2)) #running
print(power(3.2,2)) #running
print(power(4, 1.2)) #inf loop
print(power(2, -1)) #inf loop

Done.

Question 3: Greatest Common Divisor

GCD is the largest positive integer that divides the numbers without a remainder

GCD(8,12) = 4

8 = 2*2*2

12 = 2*2*3

GCD(48,18) #EuclideanAlgorithm

Step 1: 48/18 = 2, remainder 12

Step 2: 18/12 = 1, remainder 6

Step 3: 12/6 = 2, remainder 0

GCD(a,0) = a Base case

GCD(a,b) = GCD(b, a%b) This is our recursive case

For unintentional case - Positive integers, and we need to make negative number into positive number because gcd (positive number) = gcd(negative number)

def gcd(a,b): 
    assert int(a) == a and int(b) == b, "The numbers must be integer only"
    if  a < 0: 
        a = -1 * a 
    if b < 0: 
        b = -1 * b
    if b == 0: 
        return a 
    else: 
        return gcd(b, a%b) 

gcd(48, 18)
print(gcd(48, 1.8))

Done.

Question 4: Decimal to Binary

How to convert a number from decimal to binary number

Step 1: Recursive base - the flow

• Divide the number by 2

• Get the integer quotient for the next iteration

• Get the remainder dot the binary digit

• Repeat the steps until the quotient is equal to 0

f(n) = n%2 + 10* f(n/2)

Step 2 : Base case - the stopping criterion

We can see from the first step that when the number turns into 0, it stops. So if we use 0 as a param, the function will stop. And this will be out base case

Step 3: Unintentional case - the constraint

Let's search it by running different numbers and check for which case it's getting into infinity loop.

def binary(n)
    assert int(n) == n, "The param should be integer only!"
    if n == 0: 
        return 1 
    else: 
        return n%2 + 10 * binary(int(n/2))

print(binary(10))
print(binary(1.2))

End.