Practice Questions for Recursion | Set 7
Last Updated :
20 Feb, 2023
Question 1 Predict the output of the following program. What does the following fun() do in general?
C++
#include <iostream>
using namespace std;
int fun(int n, int* fp)
{
int t, f;
if (n <= 2) {
*fp = 1;
return 1;
}
t = fun(n - 1, fp);
f = t + *fp;
*fp = t;
return f;
}
int main()
{
int x = 15;
cout << fun(5, &x) << endl;
return 0;
}
|
C
#include <stdio.h>
int fun(int n, int* fp)
{
int t, f;
if (n <= 2) {
*fp = 1;
return 1;
}
t = fun(n - 1, fp);
f = t + *fp;
*fp = t;
return f;
}
int main()
{
int x = 15;
printf("%d\n", fun(5, &x));
return 0;
}
|
Java
import java.io.*;
class GFG {
static int fp = 15;
static int fun(int n)
{
int t, f;
if (n <= 2) {
fp = 1;
return 1;
}
t = fun(n - 1);
f = t + fp;
fp = t;
return f;
}
public static void main(String[] args)
{
System.out.println(fun(5));
}
}
|
Python3
fp = 15
def fun(n):
global fp
if (n <= 2):
fp = 1
return 1
t = fun(n - 1)
f = t + fp
fp = t
return f
print(fun(5))
|
C#
using System;
class GFG {
static int fp = 15;
static int fun(int n)
{
int t, f;
if (n <= 2) {
fp = 1;
return 1;
}
t = fun(n - 1);
f = t + fp;
fp = t;
return f;
}
static public void Main() { Console.Write(fun(5)); }
}
|
Javascript
<script>
var fp = 15;
function fun( n )
{
var t, f;
if ( n <= 2 )
{
fp = 1;
return 1;
}
t = fun ( n - 1 );
f = t + fp;
fp = t;
return f;
}
document.write(fun(5));
</script>
|
Time complexity: O(n)
Auxiliary Space: O(1)
The program calculates n-th Fibonacci Number. The statement t = fun ( n-1, fp ) gives the (n-1)th Fibonacci number and *fp is used to store the (n-2)th Fibonacci Number. The initial value of *fp (which is 15 in the above program) doesn’t matter. The following recursion tree shows all steps from 1 to 10, for the execution of fun(5, &x).
(1) fun(5, fp)
/ \
(2) fun(4, fp) (8) t = 3, f = 5, *fp = 3
/ \
(3) fun(3, fp) (7) t = 2, f = 3, *fp = 2
/ \
(4) fun(2, fp) (6) t = 1, f = 2, *fp = 1
/
(5) *fp = 1
Question 2: Predict the output of the following program.
C++
#include <iostream>
using namespace std;
void fun(int n)
{
if (n > 0) {
fun(n - 1);
cout << n << " ";
fun(n - 1);
}
}
int main()
{
fun(4);
return 0;
}
|
C
#include <stdio.h>
void fun(int n)
{
if (n > 0) {
fun(n - 1);
printf("%d ", n);
fun(n - 1);
}
}
int main()
{
fun(4);
return 0;
}
|
Java
import java.util.*;
class GFG {
static void fun(int n)
{
if (n > 0) {
fun(n - 1);
System.out.print(n + " ");
fun(n - 1);
}
}
public static void main(String[] args) { fun(4); }
}
|
Python3
def fun(n):
if(n > 0):
fun(n - 1)
print(n, end=" ")
fun(n - 1)
fun(4)
|
C#
using System;
class GFG {
static void fun(int n)
{
if (n > 0) {
fun(n - 1);
Console.Write(n + " ");
fun(n - 1);
}
}
static public void Main() { fun(4); }
}
|
Javascript
<script>
function fun(n)
{
if(n > 0)
fun(n - 1);
document.write(n+" ")
fun(n - 1);
}
fun(4)
</script>
|
Output
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Time complexity: O(n)
Auxiliary Space: O(1)
fun(4)
/
fun(3), print(4), fun(3) [fun(3) prints 1 2 1 3 1 2 1]
/
fun(2), print(3), fun(2) [fun(2) prints 1 2 1]
/
fun(1), print(2), fun(1) [fun(1) prints 1]
/
fun(0), print(1), fun(0) [fun(0) does nothing]
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...