Python Interview Questions on Recursion

We have compiled most frequently asked Python Interview Questions which will help you with different expertise levels.

Python Interview Questions on Recursion

When a function makes a call to itself it is called recursion. The same sets of instructions are repeated again and again for new values and it is important to decide when the recursive call must end. For Example: Let’s look at the code to find the factorial of a number.
If we use a loop then a factorial function would look something like this:

Code

def factorial(number):
j = 1
if number==0|number==1:
print(j)
else:
for i in range (1, number+1):
print(j," * ",i," = ",j*i)
j = j*i
print(j)

Execution

factorial(5)

Output

1 * 1 = 1
1 * 2 = 2
2 * 3 = 6
6 * 4 = 24
24 * 5 = 120
120
>>>

Now, let’s have a look at how we can solve the same problem using a recursive algorithm.

Code

def factorial(number):
j = 1
if number==0 | number==1:
return j
else:
return number*factorial(number-1)

Execution

print(factorial(4))

Output
24

Pros and Cons

Recursive functions make the code look neat, it helps in breaking a complex task into simpler sub-problems. It can be easier than implementing iterations. However, it can be a little difficult to understand the logic behind recursion. Recursion can consume more memory and time and can be hard to debug.

Question 1.
Write code to find the sum of natural numbers from 0 to the given number using recursion.

 I Result 0 0 1 1+0=i(1)+i(0)=1 2 2+1=i+i(1)=3 3 3+3=i+i(2)=6 4 4+6=i+i(3)=10 5 5+10=i+i(4)=15

Observe for i = 0, the result is 0, thereafter result = i(n)+i(n-l)

Code

def natural sum(num):
if num == 0
return 0
else:
return (num + natural sum(num-1) )

Execution

print (natural_sum(10))

Output

55

Question 2.
What would be the output for the following code?

def funny (x,y):
if y == 1:
return x [0]
else:
a = funny (x, y-1)
if a>x [y-1]
return a
else:
return x[y-1]
x = [1,5,3,6,7]
y = 3
print (funny (x,y) )

If we insert a print statement in the code and execute the code again we can see the actual sequence in which it executes:

def funny(x,y):
print("calling funny , y = ",y)
if y == 1:
return x[0]
else:

print("inside else loop because y = ", y)
a = funny(x, y-1)
print("a = ", a)
if a > x[y-1]:
print("a = ",a, " Therefore a > ",x[y-1])
return a
else:
print("a = ",a, " Therefore a < ",x[y-1])
return x[y-1]
x = [1,5,3,6,7]
y = 3
print(funny(x,y))

Output

calling funny , y = 3
inside else loop because y = 3
calling funny , y = 2
inside else loop because y = 2
calling funny , y = 1
a = 1
a = 1 Therefore a < 5
a = 5
a = 5 Therefore a > 3
5
The answer is 5

Question 3.
What would be the output of the following code?

def funny(x):
if (x%2 == 1) :
return x+1
else:
return funny(x-1)
print(funny(7))
print(funny(6))

For x =7
1. x = 7
2. x % 2 is 1
return 7 + 1
For x = 6
1. x =6
2. x%2 = 0
3. Return funny(5)
4. x = 5 .
5. x%2 =1
6. Return x+1 = 6

Question 4.
Write Fibonacci sequence using recursion. Answer:
The Fibonacci sequence = 0, 1, 2, 3, 5, 8, 13 ……….

 I Result 0 0 1 1 2 1+0=i(0)+i(1)=1 3 1+1=i(2)+i(1)=2 4 2+1=i(3)+i(2)=3 5 3+2=i(4)+i(3)=5

Observe for i = 0, the result is 0 and for i = 1, the result is 1. Thereafter, the value of i(n) = i(n-1) + i(n-2). We implement the same, when we try to find Fibonacci code using recursion.

• The fibonacci_seq(num), takes a number as argument.
• If num = 0, result is 0
• If num = 1, result is 1
• Else result is fibonacci_seq(num-l) + Fibonacci_seq(num-2)
• If you want to find Fibonacci Sequence for 10 then:
• For elements 0 to 10 o Call the fibonacci_seq( ) function
• fibonacci_seq(0) = 0
• fibonacciseq(l) = 1
• fibonacci_seq(2) = fibonacci_seq(l)+ fibonacci_seq(0)
• fibonacci_seq(3) = fibonacci_seq(2)+ fibonacci_seq(3)

Code

def fibonacci_seq (num) :
if num <0:
print("Please provide a positive integer value")
if num == 0:
return 0
elif num == 1:
return 1
else:
return (fibonacci_seq (num-1) +fibonacci_ seq(num-2))

Execution

for i in range(10):
print (fibonacci_seq(i))

Output

0
1
1
2
3
5
8
13
21
34

Question 5.
What is memoization?
Basically, in memoization, we maintain a look-up table where solutions are stored so that we don’t have to solve the same sub-problem again and again. Instead, we solve it once and store the values so that they can be reused.

We know that Fibonacci sequence is:
F(n) = F(n-1)+F(n-2) if n>1 = n if n =0,1
So,
F(n):
if n<1:
return n
else :
return F(n-1)+F(n-2)
Here, we are making two recursive calls and adding them up and the value is returned.
Look at the following diagram:

Just to find Fibonacci(5), Fibonacci(2) is computed three times and Fibonacci (3) is computed two times. So, as n increases Fibonacci function’s performance will go down. The consumption of time and space would increase exponentially with an increase in n. In order to save time what we can do is save a value when it is computed for the first time. So, we can save F(2) when it is computed for the first time, the same way with F(3), F(4)… so on. So, we can say that:

F(n):
if n=<1:
return n
elif f(n) exist:
return F(n-1)
else:
F(n) = F(n-1) + F(n-2)
save F(n).
Return F(n).

In the code below:

1. The function Fibonacci( ) takes a number and creates a list, fib_num of size num+1. This is because the Fibonacci series starts from 0.
2. It calls the function fib_calculate( )which takes the number num and lists fib_num as a parameter.
3. We have saved-I at all index in the list:

a. If fib_num[num] is>0, that means Fibonacci for this number already exists and we need not compute it again and the number can be returned.
b. If num <= 1 then return num.
c. Else if num >=2, calculate fib_calculate(num – 1, fib num) + fib_calculate(num – 2, fib_num). The value calculated must be stored in list fib_num at index num so that there is no need to calculate it again.

Code

def fibonacci (num) :

fib_num = [-1] * (num + 1)
return fib_calculate (num, fib_num)
def fib_calculate (num, fib_num) :
if fib_num [num] >= 0:
return fib_num[num]

if (num <= 1):
fnum = num
else:
fnum = fib_calculate (num - 1, fib_num) + fib_ calculate (num - 2, fib_num)
fib_num [num] = fnum

return fnum

Execution

num = int(input('Enter the number: '))
print ("Answer = ", fibonacci (num) )

Output

Enter the number: 15
>>>

Question 6.
What would be the output of the following program?

def test_function(i, j) :
if i == 0:
return j;
else:
return test_function(i-1, j+1)
print (test_function(6,7) )

 I J I==0? Return 6 7 No Test_function(5,8) 5 8 No Test_function(4,9) 4 9 No Test_function(3,10) 3 10 No Test_function(2,11) 2 11 No Test_function(1,12) 1 12 No Test_function(0,13) 0 13 Yes 13

The output will be 13.

Question 7.
What will be the output for the following code:

def even(k):
if k <= 0:
elif k == 1:
return 0
else:
return even(k-1) + 2
print(even(6))

 K K<=0 K ==1 Result 6 no No Even(5)+2 5 No No Even(4)+2+2 4 No No Even(3)+2+2+2 3 No No Even(2)+2+2+2+2 2 No No Even(1)+2+2+2+2+2 1 No yes 0)+2+2+2+2+2

Question 8.
Write a code to find the n_power(n), of 3 using recursion. Answer:
1. Define function n_power(n), it takes the value of power and parameter(n).
2. If n = 0 then return 1 because any number raised to power 0 is 1.
3. Else return (n_power(n-1)).

 N N<0 N ==0 Result 4 No No n_power(3)*3 3 No No n_power(2)*3*3 2 No No n_power(1)*3*3*3 1 No No n_power(0)*3*3*3*3 0 No Yes 1*3*3*3*3

Code

def n_power(n):
if n < 0:
print ("please enter a positive value")
elif n == 0:
return 1
else:
return n_power(n-1)*3

Execution

print(n_power(4))

Output

81