Практические вопросы для рекурсии | Комплект 7

Опубликовано: 21 Января, 2022

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 <= 1 )
    {
        *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;
}
 
// This code is contributed by shubhamsingh10

C

#include <stdio.h>
 
int fun ( int n, int *fp )
{
    int t, f;
 
    if ( n <= 1 )
    {
        *fp = 1;
        return 1;
    }
    t = fun ( n-1, fp );
    f = t + *fp;
    *fp = t;
    return f;
}
 
int main()
{
    int x = 15;
    printf("%d ",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 <= 1 )
        {
            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));
    }
}
// This code is contributed by shubhamsingh10

Python3

fp = 15
def fun ( n ):
    global fp
    if ( n <= 1 ):
        fp = 1
        return 1
     
    t = fun ( n - 1 )
    f = t + fp
    fp = t
    return f
 
# Driver code
 
print(fun(5))
 
# This code is contributed by shubhamsingh10

C#

using System;
  
class GFG{
    static int fp = 15;
    static int fun ( int n)
    {
        int t, f;
     
        if ( n <= 1 )
        {
            fp = 1;
            return 1;
        }
        t = fun ( n - 1 );
        f = t + fp;
        fp = t;
        return f;
    }
     
    static public void Main ()
    {
        Console.Write(fun(5));
    }
}
// This code is contributed by shubhamsingh10

Javascript

<script>
//Javascript Implementation
var fp = 15;
function fun( n )
{
    var t, f;
  
    if ( n <= 1 )
    {
        fp = 1;
        return 1;
    }
    t = fun ( n - 1 );
    f = t + fp;
    fp = t;
    return f;
}
 
// Driver Code
 
document.write(fun(5));
 
// This code is contributed by shubhamsingh10
 
</script>

Выход:

 8

Программа рассчитывает n-е число Фибоначчи. Выражение t = fun (n-1, fp) дает (n-1) -ое число Фибоначчи, а * fp используется для хранения (n-2) -го числа Фибоначчи. Начальное значение * fp (которое в приведенной выше программе равно 15) не имеет значения. Следующее дерево рекурсии показывает все шаги с 1 по 10 для выполнения fun (5, & x).

 (1) веселье (5, fp)
                              / 
                         (2) fun (4, fp) (10) t = 5, f = 8, * fp = 5
                         / 
                   (3) fun (3, fp) (9) t = 3, f = 5, * fp = 3
                  / 
           (4) fun (2, fp) (8) t = 2, f = 3, * fp = 2
          / 
   (5) fun (1, fp) (7) t = 1, f = 2, * fp = 1
   /
(6) * fp = 1

Вопрос 2: Предскажите результат следующей программы.

Выход:

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

веселье (4)
                   /
                веселье (3), печать (4), веселье (3) [веселье (3) печатает 1 2 1 3 1 2 1]
               /
           веселье (2), печать (3), веселье (2) [веселье (2) печатает 1 2 1]
           /
       веселье (1), печать (2), веселье (1) [веселье (1) печатает 1]
       /
    fun (0), print (1), fun (0) [fun (0) ничего не делает]

Пожалуйста, напишите комментарии, если вы обнаружите, что какой-либо из ответов / кодов неверен, или вы хотите поделиться дополнительной информацией / вопросами по темам, обсужденным выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.