Recursion

Question 1

What is recursion

Answer 1

A function calling itself

Question 2

Which DS is used to solve recursion

Answer 2

STACK

Question 3

Every function call has its own?

Answer 3

Stack space and local variables

Question 4

If no termination condition present in recursive program then what happens

Answer 4

Stack overflow which is a runtime error

Question 5

For every recursive program, is non recursive program present?

Answer 5

Yes

Question 6

Time complexity comparison of recursive and non recursive program for same algo

Answer 6

Same

Question 7

Space complexity comparison of recursive and non recursive program for same algo

Answer 7

Space complexity of recursive program is more

Question 8

Amount of stack space used by recursive program

Answer 8

Depth of stack

Question 9

From one call to another call of a recursive prog does code, no. of parameters, name of parameter change?

Answer 9

No only value of parameters can change

Question 10

Methods for solving recursive problems

Answer 10

Substitution, Recursive tree, Masters theorem

Question 11

Constant time corresponds to

Answer 11

O(1)

Question 12

For multiplication by recursion no. of additions for doing m*n

Answer 12

0 if m=0 or n=0
A(m,n-1)+1 if n>0 and m>0

Question 12

For fibonacci series nth no., no. of additions

Answer 12

0 if n=0 or n=1(n<=1)
fib(n-1)+fib(n-2)+1

Question 13

Substitution

Answer 13

Substitute until u get a pattern

Question 14

1+2+3+—–+n

Answer 14

n(n+1)/2

Question 15

123—–n

Answer 15

n!

Question 16

Sum of squares of natural nos.

Answer 16

n(n+1)(2n+1)/6

Question 17

Which log considered in TC

Answer 17

log base 2

Question 18

(log n)^2

Answer 18

log^2 n

Question 19

In infinite loop , why is there no stack overflow

Answer 19

Because only one function call

Question 20

AGP solve method

Answer 20

FInd T(n)
Find 2T(n)
Do T(n)-2T(n)
Find -T(n)

Question 21

Recursive tree

Answer 21

Find leftmost length, rightmost length and then evaluate upper and lower bounds

Question 22

Tree height in recursive tree

Answer 22

Stack space is tree height

Question 23

Decreasing GP value gives

Answer 23

O(1)

Question 24

Log property a ^ log b c

Answer 24

= c ^ log b a