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 >>>
- Python Program to Count Divisors of Factorial
- Python Program to Print Numbers in a Range (1,upper) Without Using any Loops or by Using Recursion
- Python Program to Find if a Number is Prime or Not Prime Using Recursion
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.
Answer:
| 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) )
Answer:
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))
Answer:
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?
Answer:
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:
- 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.
- It calls the function fib_calculate( )which takes the number num and lists fib_num as a parameter.
- 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 Answer = 610 >>>
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) )
Answer:
| 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:
print("please enter a positive value")
elif k == 1:
return 0
else:
return even(k-1) + 2
print(even(6))
Answer:
| 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