Practice Questions for Recursion | Set 6
Last Updated :
21 Aug, 2022
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++
void abc(char *s)
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
cout << s[0];
}
|
C
void abc(char *s)
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
printf("%c", s[0]);
}
|
Java
static void abc(char *s)
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
System.out.print(s[0]);
}
|
Python3
def abc(s):
if(len(s) == 0):
return
abc(s[1:])
abc(s[1:])
print(s[0])
|
C#
static void abc(char *s)
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
Console.Write(s[0]);
}
|
Javascript
<script>
function abc(s)
{
if(s.length == 0)
return;
abc(s.substring(1));
abc(s.substring(1));
document.write(s[0]);
}
</script>
|
Time complexity: O(2n)
Auxiliary Space: O(n)
The following is the relationship between num and len.
num = 2^len-1
s[0] is 1 time printed
s[1] is 2 times printed
s[2] is 4 times printed
s[i] is printed 2^i times
s[strlen(s)-1] is printed 2^(strlen(s)-1) times
total = 1+2+....+2^(strlen(s)-1)
= (2^strlen(s)) - 1
For example, the following program prints 7 characters.
C++
#include <bits/stdc++.h>
using namespace std;
void abc(char s[])
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
cout << s[0];
}
int main()
{
abc("xyz");
return 0;
}
|
C
#include<stdio.h>
void abc(char *s)
{
if(s[0] == '\0')
return;
abc(s + 1);
abc(s + 1);
printf("%c", s[0]);
}
int main()
{
abc("xyz");
return 0;
}
|
Java
public class GFG
{
static void abc(String s)
{
if(s.length() == 0)
return;
abc(s.substring(1));
abc(s.substring(1));
System.out.print(s.charAt(0));
}
public static void main(String[] args) {
abc("xyz");
}
}
|
Python3
def abc(s):
if(len(s) == 0):
return
abc(s[1:])
abc(s[1:])
print(s[0],end="")
abc("xyz")
|
C#
using System;
class GFG {
static void abc(string s)
{
if(s.Length == 0)
return;
abc(s.Substring(1));
abc(s.Substring(1));
Console.Write(s[0]);
}
static void Main() {
abc("xyz");
}
}
|
Javascript
<script>
function abc(s)
{
if(s.length == 0)
return;
abc(s.substring(1));
abc(s.substring(1));
document.write(s[0]);
}
abc("xyz");
</script>
|
Thanks to bharat nag for suggesting this solution.
Question 2
C++
#include <iostream>
using namespace std;
int fun(int count)
{
cout << count << endl;
if(count < 3)
{
fun(fun(fun(++count)));
}
return count;
}
int main()
{
fun(1);
return 0;
}
|
C
#include<stdio.h>
int fun(int count)
{
printf("%d\n", count);
if(count < 3)
{
fun(fun(fun(++count)));
}
return count;
}
int main()
{
fun(1);
return 0;
}
|
Java
import java.util.*;
class GFG{
static int fun(int count)
{
System.out.println(count);
if(count < 3)
{
fun(fun(fun(++count)));
}
return count;
}
public static void main(String[] args)
{
fun(1);
}
}
|
Python3
def fun(count):
print(count)
if(count < 3):
count+=1
fun(fun(fun(count)))
return count
if __name__=="__main__":
fun(1)
|
C#
using System;
class GFG{
static int fun(int count)
{
Console.Write(count+"\n");
if(count < 3)
{
fun(fun(fun(++count)));
}
return count;
}
static public void Main ()
{
fun(1);
}
}
|
Javascript
<script>
function fun(count)
{
document.write(count + "</br>");
if(count < 3)
{
fun(fun(fun(++count)));
}
return count;
}
fun(1);
</script>
|
Output:
1
2
3
3
3
3
3
The main() function calls fun(1). fun(1) prints “1” and calls fun(fun(fun(2))). fun(2) prints “2” and calls fun(fun(fun(3))). So the function call sequence becomes fun(fun(fun(fun(fun(3))))). fun(3) prints “3” and returns 3 (note that the count is not incremented and no more functions are called as if the condition is not true for count 3). So the function call sequence reduces to fun(fun(fun(fun(3)))). fun(3) again prints “3” and returns 3. So the function call again reduces to fun(fun(fun(3))) which again prints “3” and reduces it to fun(fun(3)). This continues and we get “3” printed 5 times on the screen.
Time complexity: O(2n)
Auxiliary Space : O(n), since n extra space has been taken.
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.
Please Login to comment...