Practice Questions for Recursion | Set 5

Question 1
Predict the output of the following program. What does the following fun() do in general?  

#include <iostream> 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 << fun(4, 3) ;   return 0;  }  // This code is contributed by SHUBHAMSINGH10 

#include<stdio.h> 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() {  printf("%d", fun(4, 3));  getchar();  return 0; } 

/*package whatever //do not write package name here */ import java.io.*; class GFG {  static 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;   }     public static void main (String[] args)   {  System.out.println(fun(4, 3));  } } // This code is contributed by SHUBHAMSINGH10 

def fun(a, b): if (b == 0): return 0 if (b % 2 == 0): return fun(a + a, b//2) return fun(a + a, b//2) + a # Driver code print(fun(4, 3)) # This code is contributed by SHUBHAMSINGH10 

using System; class GFG{  static 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;   }     static public void Main ()   {   Console.Write(fun(4, 3));   }  } // This code is contributed by SHUBHAMSINGH10 

<script> //Javascript Implementation function fun(a, b) {  if (b == 0)  return 0;  if (b % 2 == 0)  return fun(a + a, Math.floor(b/2));    return fun(a + a, Math.floor(b/2)) + a; } document.write(fun(4, 3)); // This code is contributed by shubhamsingh10 </script> 

12

It calculates a*b (a multiplied b).

Time Complexity: O(log₂(b))
Auxiliary Space:  O(log₂(b))

Question 2 
In question 1, if we replace + with * and replace return 0 with return 1, then what does the changed function do? Following is the changed function. 

#include <iostream> using namespace std;   int fun(int a, int b)  {   if (b == 0)   return 1;   if (b % 2 == 0)   return fun(a*a, b/2);     return fun(a*a, b/2)*a;  }    int main()  {   cout << fun(4, 3) ;   getchar();   return 0;  }  //This code is contributed by shubhamsingh10 

#include<stdio.h> int fun(int a, int b) {  if (b == 0)  return 1;  if (b % 2 == 0)  return fun(a*a, b/2);  return fun(a*a, b/2)*a; } int main() {  printf("%d", fun(4, 3));  getchar();  return 0; } 

import java.io.*;   class GFG {  static int fun(int a, int b)   {   if (b == 0)   return 1;   if (b % 2 == 0)   return fun(a*a, b/2);     return fun(a*a, b/2)*a;   }     public static void main (String[] args)  {   System.out.println(fun(4, 3));   }  } //This code is contributed by shubhamsingh10 

def fun(a, b): if (b == 0): return 1 if (b % 2 == 0): return fun(a*a, b//2) return fun(a*a, b//2)*a # Driver code print(fun(4, 3)) # This code is contributed by shubhamsingh10 

using System; public class GFG{    static int fun(int a, int b)   {   if (b == 0)   return 1;   if (b % 2 == 0)   return fun(a*a, b/2);     return fun(a*a, b/2)*a;   }       static public void Main ()  {   Console.WriteLine(fun(4, 3));   }  } // This code is contributed by shubhamsingh10 

<script> //Javascript Implementation function fun(a, b) {  if (b == 0)  return 1;  if (b % 2 == 0)  return fun(a * a, Math.floor(b/2));    return fun(a * a, Math.floor(b/2)) * a; } document.write(fun(4, 3)); // This code is contributed by shubhamsingh10 </script> 

64

It calculates a^b (a raised to power b).
Time complexity: O(log₂b)
Auxiliary Space: O(log₂b)

Question 3 
Predict the output of the following program. What does the following fun() do in general?  

#include <iostream> using namespace std; int fun(int n) {  if (n > 100)  return n - 10;  return fun(fun(n+11)); } int main() {  cout << " " << fun(99) << " ";  getchar();  return 0; } // This code is contributed by Shubhamsingh10 

#include<stdio.h>  int fun(int n)  {  if (n > 100)  return n - 10;  return fun(fun(n+11));  } int main() {  printf(" %d ", fun(99));  getchar();  return 0; } 

import java.io.*; class GFG {  static int fun(int n)  {  if (n > 100)  return n - 10;  return fun(fun(n+11));  }    public static void main (String[] args) {  System.out.println(" " + fun(99) + " ");  } } // This code is contributed by Shubhamsingh10 

def fun(n): if (n > 100): return n - 10 return fun(fun(n + 11)) # Driver code print(fun(99)) # This code is contributed by Shubhamsingh10 

using System; class GFG{   static int fun(int n) {  if (n > 100)  return n - 10;  return fun(fun(n + 11)); } // Driver code  static public void Main () {   Console.WriteLine(fun(99)); } } // This code is contributed by Shubhamsingh10 

<script> function fun(n) {  if (n > 100)  return n - 10    return fun(fun(n + 11)) }   // Driver code document.write(fun(99)) // This code is contributed by Bobby Gottumukkala </script> 

91

fun(99) = fun(fun(110)) since 99 ? 100 = fun(100) since 110 > 100 = fun(fun(111)) since 100 ? 100 = fun(101) since 111 > 100 = 91 since 101 > 100

Time complexity: O(n)
Auxiliary Space: O(n), to maintain function call into call stack

The returned value of fun() is 91 for all integer arguments n 101. This function is known as McCarthy 91 function. 
Please write comments if you find any of the answers/codes incorrect, or you want to share more information/questions about the topics discussed above.