Open In App

Practice Questions for Recursion | Set 2

Last Updated : 25 Apr, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Explain the functionality of the following functions. 

Question 1 

C++




/* Assume that n is greater than or equal to 1 */
int fun1(int n)
{
    if (n == 1)
        return 0;
    else
        return 1 + fun1(n / 2);
}
 






                        









Java














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















/* Assume that n is greater than or equal to 1 */


static int fun1(int n)


{


    if (n == 1)


        return 0;


    else


        return 1 + fun1(n / 2);


}



















                        







                        









Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















# Assume that n is greater than or equal to 1 */


def fun1(n):


    if(n == 1):


        return 0


    else:


        return 1 + fun1(n//2)



















                        







                        









C#














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















/* Assume that n is greater than or equal to 1 */


static int fun1(int n)


{


    if (n == 1)


        return 0;


    else


        return 1 + fun1(n / 2);


}



















                        







                        









Javascript














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















<script>


 


/* Assume that n is greater than or equal to 1 */


function fun1(n)


{


    if (n == 1)


        return 0


    else


        return 1 + fun1(Math.floor(n / 2))


}


</script>



















                        







                        












Answer: The function calculates and returns log2floor




For example, if n is between 8 and 15 then fun1() returns 3. If n is between 16 to 31 then fun1() returns 4.


Question 2 




C++














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















/* Assume that n is greater than or equal to 0 */


void fun2(int n)


{


if(n == 0)


    return;


 


fun2(n/2);


cout << n%2 << endl;


}



















                        







                        









C














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















/* Assume that n is greater than or equal to 0 */


void fun2(int n)


{


  if(n == 0)


    return;


 


  fun2(n/2);


  printf("%d", n%2);


}  



















                        







                        









Java














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















/* Assume that n is greater than or equal to 1 */


static void fun2(int n)


{


if(n == 0)


    return;


  


fun2(n/2);


System.out.println(n%2);


} 



















                        







                        









Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















# Assume that n is greater than or equal to 0 */


def fun2(n):


    if(n == 0):


        return


     


    fun2(n // 2)


    print(n % 2, end="")



















                        







                        









C#














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















void fun2(int n) 


{ 


if(n == 0) 


    return; 


   


fun2(n/2); 


Console.Write(n%2); 


} 



















                        







                        









Javascript














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















<script>


 


// Assume that n is greater than or equal to 1 


function fun2(n)


{


    if (n == 0)


        return;


     


    fun2(Math.floor(n / 2));


    document.write(n % 2 + " ")


}


</script>



















                        







                        










Auxiliary Space: O(log2N), due to recursion call stack


Time Complexity: O(log N)


Answer: The function fun2() prints the binary equivalent of n. For example, if n is 21 then fun2() prints 10101. 




Note: Above functions are just for practicing recursion, they are not the ideal implementation of the functionality they provide. 




Please write comments if you find any of the answers/codes incorrect. 




                                    


                                                                        

                                        

                                            

                                                

                                                    

        https://media.geeksforgeeks.org/auth/avatar.png
       
                                                

                                                

                                                    
    

        

            GeeksforGeeks
        

    
                                                

                                            

                                                                                    

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                                                            

                                    
                                        
                                        Previous Article
                                    
                                    
                                    

                                        Practice Questions for Recursion | Set 1
                                    

                                

                                                            

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Practice Questions for Recursion | Set 3
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Practice Questions for Recursion | Set 1

                
Explain the functionality of the following functions. Question 1 C/C++ Code int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } C/C++ Code int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } Java Code static int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } C/C

            

            
            

                
                5 min read
            

        
    
        
            

                
Practice Questions for Recursion | Set 4

                
Question 1 Predict the output of the following program. C/C++ Code #include &lt;iostream&gt; using namespace std; void fun(int x) { if(x &gt; 0) { fun(--x); cout &lt;&lt; x &lt;&lt;&quot; &quot;; fun(--x); } } int main() { int a = 4; fun(a); return 0; } // This code is contributed by SHUBHAMSINGH10 C/C++ Code #include&lt;stdio.h&gt; void fun(int x)

            

            
            

                
                6 min read
            

        
    
        
            

                
Practice Questions for Recursion | Set 5

                
Question 1Predict the output of the following program. What does the following fun() do in general? C/C++ Code #include &lt;iostream&gt; using namespace std; int fun(int a, int b) { if (b == 0) return 0; if (b % 2 == 0) return fun(a + a, b/2); return fun(a + a, b/2) + a; } int main() { cout &lt;&lt; fun(4, 3) ; return 0; } // This code is contribut

            

            
            

                
                5 min read
            

        
    
        
            

                
Practice Questions for Recursion | Set 6

                
Question 1 Consider the following recursive C function. Let len be the length of the string s and num be the number of characters printed on the screen. Give the relation between num and len where len is always greater than 0. C/C++ Code void abc(char *s) { if(s[0] == '&#92;&#48;') return; abc(s + 1); abc(s + 1); cout &lt;&lt; s[0]; } // This code

            

            
            

                
                4 min read
            

        
    
        
            

                
Practice Questions for Recursion | Set 7

                
Question 1 Predict the output of the following program. What does the following fun() do in general? C/C++ Code #include &lt;iostream&gt; using namespace std; int fun(int n, int* fp) { int t, f; if (n &lt;= 2) { *fp = 1; return 1; } t = fun(n - 1, fp); f = t + *fp; *fp = t; return f; } int main() { int x = 15; cout &lt;&lt; fun(5, &amp;x) &lt;&lt;

            

            
            

                
                4 min read
            

        
    
        
            

                
Practice Questions for Recursion | Set 3

                
Explain the functionality of below recursive functions. Question 1 C/C++ Code void fun1(int n) { int i = 0; if (n &gt; 1) fun1(n - 1); for (i = 0; i &lt; n; i++) cout &lt;&lt; &quot; * &quot;; } // This code is contributed by shubhamsingh10 C/C++ Code void fun1(int n) { int i = 0; if (n &gt; 1) fun1(n-1); for (i = 0; i &lt; n; i++) printf(&quot; *

            

            
            

                
                3 min read
            

        
    
        
            

                
Practice questions for Linked List and Recursion

                
Assume the structure of a Linked List node is as follows. C/C++ Code struct Node { int data; struct Node *next; }; // This code is contributed by SHUBHAMSINGH10 C/C++ Code struct Node { int data; struct Node *next; }; Java Code static class Node { int data; Node next; }; // This code is contributed by shubhamsingh10 C/C++ Code class Node: def __ini

            

            
            

                
                11 min read
            

        
    
        
            

                
Why is Tail Recursion optimization faster than normal Recursion?

                
What is tail recursion? Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. What is non-tail recursion? Non-tail or head recursion is defined as a recursive function in which the recursive call is the f

            

            
            

                
                4 min read
            

        
    
        
            

                
Combination and Permutation Practice Questions | Set 1

                
Prerequisite : Permutation and Combination n students appear in an examination, find the number of ways the result of examination can be announced. Answer is 2n Examples: Input : n = 6 Output : Each student can either pass or fail in the examination. so ,there exists 2 possibilities for each of the 6 students in the result. hence total number of wa

            

            
            

                
                3 min read
            

        
    
        
            

                
Practice Questions on Huffman Encoding

                
Huffman Encoding is an important topic from GATE point of view and different types of questions are asked from this topic. Before understanding this article, you should have basic idea about Huffman encoding. These are the types of questions asked in GATE based on Huffman Encoding. Type 1. Conceptual questions based on Huffman Encoding - Here are t

            

            
            

                
                4 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox