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.