Open In App

Practice Questions for Recursion | Set 1

Last Updated : 20 Feb, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Explain the functionality of the following functions. 

Question 1 

C++




int fun1(int x, int y)
{
    if (x == 0)
        return y;
    else
        return fun1(x - 1, x + y);
}


C




int fun1(int x, int y)
{
    if (x == 0)
        return y;
    else
        return fun1(x - 1, x + y);
}


Java




static int fun1(int x, int y)
{
    if (x == 0)
        return y;
    else
        return fun1(x - 1, x + y);
}


Python3




def fun1(x, y) :
  
    if (x == 0) :
        return y
    else :
        return fun1(x - 1, x + y)
  
# This code is contributed by divyesh072019


C#




static int fun1(int x, int y)
{
    if (x == 0)
        return y;
    else
        return fun1(x - 1, x + y);
}
  
// This code is contributed by divyesh072019


Javascript




<script>
  
function fun1(x, y)
{
     if (x == 0) 
        return y
    else 
        return fun1(x - 1, x + y)
}
  
// This code is contributed by gottumukkalabobby
  
</script>


Answer: The function fun1() calculates and returns ((1 + 2 … + x-1 + x) +y), which is x(x+1)/2 + y. For example, if x is 5 and y is 2, then fun should return 15 + 2 = 17.

Question 2 

C++




// minimum index finder
  
int minIndex(int arr[], int s, int e)
{
    int sml = INT32_MAX;
    int mindex;
    for (int i = s; i < e; i++) {
        if (sml > arr[i]) {
            sml = arr[i];
            mindex = i;
        }
    }
    return mindex;
}
  
void fun2(int arr[], int start_index, int end_index)
{
    if (start_index >= end_index)
        return;
    int min_index;
    int temp;
  
    // minIndex() returns index of minimum value in
    // array arr[start_index...end_index] 
    min_index = minIndex(arr, start_index, end_index);
  
    // swap the element at start_index and min_index
    swap(arr[start_index], arr[min_index]);
  
    fun2(arr, start_index + 1, end_index);
}
  
// This code is contributed by nishant_0073


C




// minimum index finder
  
int minIndex(int arr[], int s, int e)
{
    int sml = INT32_MAX;
    int mindex;
    for (int i = s; i < e; i++) {
        if (sml > arr[i]) {
            sml = arr[i];
            mindex = i;
        }
    }
    return mindex;
}
  
void fun2(int arr[], int start_index, int end_index)
{
    if (start_index >= end_index)
        return;
    int min_index;
    int temp;
  
    // minIndex() returns index of minimum value in
    // array arr[start_index...end_index] 
    min_index = minIndex(arr, start_index, end_index);
  
    temp = arr[start_index];
    arr[start_index] = arr[min_index];
    arr[min_index] = temp;
  
    fun2(arr, start_index + 1, end_index);
}


Java




// minimum index finder
static int minIndex(int arr[], int s, int e)
{
    int sml = Integer.MAX_VALUE;
    int mindex = ;
    for (int i = s; i < e; i++) {
        if (sml > arr[i]) {
            sml = arr[i];
            mindex = i;
        }
    }
    return mindex;
}
  
static void fun2(int arr[], int start_index, int end_index)
{
    if (start_index >= end_index)
        return;
    int min_index;
    int temp;
  
    // minIndex() returns index of minimum value in
    //   array arr[start_index...end_index]
    min_index = minIndex(arr, start_index, end_index);
  
    temp = arr[start_index];
    arr[start_index] = arr[min_index];
    arr[min_index] = temp;
  
    fun2(arr, start_index + 1, end_index);
}
  
// This code is contributed by nishant_0073


Python3




# Minimum index finder
def minIndex(arr, s, e):
      
    sml = sys.maxsize
    mindex = 0
      
    for i in range(s, e):
        if (sml > arr[i]):
            sml = arr[i]
            mindex = i
              
    return mindex
  
def fun2(arr, start_index, end_index):
      
    if (start_index >= end_index):
        return
          
    # minIndex() returns index of minimum value in
    # array arr[start_index...end_index]
    min_index = minIndex(arr, start_index, end_index)
    arr[start_index], arr[min_index] = arr[min_index], arr[start_index]
    fun2(arr, start_index + 1, end_index)
  
# This code is contributed by rag2127


C#




// minimum index finder
static int minIndex(int[] arr, int s, int e)
{
    int sml = Int32.MaxValue;
    int mindex;
    for(int i = s; i < e; i++)
    {
        if(sml > arr[i])
        {
            sml = arr[i];
            mindex = i;
        }
    }
    return mindex;   
}
static void fun2(int[] arr, int start_index, int end_index)    
{
    if(start_index >= end_index)
    {
        return;
    }
    int min_index;
    int temp;
    
    // minIndex() returns index of minimum value in
    //   array arr[start_index...end_index]
    min_index = minIndex(arr, start_index, end_index);
    temp = arr[start_index];
    arr[start_index] = arr[min_index];
    arr[min_index] = temp;
   
    fun2(arr, start_index + 1, end_index);
}
  
// This code is contributed by avanitrachhadiya2155


Javascript




<script>
//Javascript Implementation
// minimum index finder
   
function minIndex(arr, s, e)
{
    var sml = Number.MAX_SAFE_INTEGER;
    var mindex;
    for (int i = s; i < e; i++) {
        if (sml > arr[i]) {
            sml = arr[i];
            mindex = i;
        }
    }
    return mindex;
}
   
function fun2(arr, start_index, end_index)
{
    if (start_index >= end_index)
        return;
    var min_index;
    var temp;
   
    // minIndex() returns index of minimum value in
    // array arr[start_index...end_index]
    min_index = minIndex(arr, start_index, end_index);
   
    // swap the element at start_index and min_index
    temp = arr[start_index];
    arr[start_index] = arr[min_index];
    arr[min_index] = temp;
   
    fun2(arr, start_index + 1, end_index);
}
// This code is contributed by shubhamsingh10
</script>


Answer: The function fun2() is a recursive implementation of Selection Sort.

Time complexity: O(N2)

Auxiliary Space: O(1)

Please write comments if you find any of the answers/codes incorrect, or you want to share more information about the topics discussed above.
 



Previous Article
Next Article

Similar Reads

Practice Questions for Recursion | Set 2
Explain the functionality of the following functions. Question 1 C/C++ Code /* 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 Code /* 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); } C/C++ Code # As
3 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 :