Preguntas de práctica para la recursividad | conjunto 6

Pregunta 1 
Considere la siguiente función C recursiva. Sea len la longitud de la string s y num el número de caracteres impresos en la pantalla. Dé la relación entre num y len donde len siempre es mayor que 0. 

void abc(char *s)
{
    if(s[0] == '\0')
        return;
  
    abc(s + 1);
    abc(s + 1);
    cout << s[0];   
}
 
// This code is contributed by shubhamsingh10

void abc(char *s)
{
    if(s[0] == '\0')
        return;
 
    abc(s + 1);
    abc(s + 1);
    printf("%c", s[0]);   
}

static void abc(char *s)
{
    if(s[0] == '\0')
        return;
   
    abc(s + 1);
    abc(s + 1);
    System.out.print(s[0]);   
}
 
// This code is contributed by shubhamsingh10

def abc(s):
    if(len(s) == 0):
        return
     
    abc(s[1:])
    abc(s[1:])
    print(s[0])
     
# This code is contributed by shubhamsingh10

static void abc(char *s)
{
    if(s[0] == '\0')
        return;
 
    abc(s + 1);
    abc(s + 1);
    Console.Write(s[0]);
}
 
// This code is contributed by shubhamsingh10

<script>
//Javascript Implementation
function abc(s)
{
    if(s.length == 0)
        return;
         
    abc(s.substring(1));
    abc(s.substring(1));
    document.write(s[0]);   
}
 
// This code is contributed by shubhamsingh10
</script>

Complejidad del tiempo: O(2 ⁿ )

Espacio Auxiliar: O(n)
 

La siguiente es la relación entre num y 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

Por ejemplo, el siguiente programa imprime 7 caracteres. 

#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;
}
//This code is contributed by shubhamsingh10

#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;
}

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");
    }
}
 
// This code is contributed by divyeh072019

def abc(s):
    if(len(s) == 0):
        return
     
    abc(s[1:])
    abc(s[1:])
    print(s[0],end="")
 
 
# Driver code
 
abc("xyz")
 
# This code is contributed by shubhamsingh10

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]);
    }
 
  // Driver code
  static void Main() {
    abc("xyz");
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
// Javascript implementation
 
function abc(s)
{
    if(s.length == 0)
        return;
 
    abc(s.substring(1));
    abc(s.substring(1));
    document.write(s[0]);
}
 
abc("xyz");
 
//This code is contributed by shubhamsingh10
</script>

Gracias a bharat nag por sugerir esta solución. 
 

Pregunta 2 

#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;
}
 
// This code is contributed by Shubhamsingh10

#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;
}

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);
}
}
 
// This code is contributed by Shubhamsingh10

def fun(count):
    print(count)
    if(count < 3):
        count+=1
        fun(fun(fun(count)))
     
    return count
  
 
if __name__=="__main__": 
     
    fun(1)
 
# This code is contributed by Shubhamsingh10

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

<script>
 
    function fun(count)
    {
        document.write(count + "</br>");
        if(count < 3)
        {
            fun(fun(fun(++count)));
        }
        return count;
    }
     
    fun(1);
 
</script>

Producción: 

 1
 2
 3
 3
 3
 3
 3

La función main() llama a fun(1). fun(1) imprime “1” y llama a fun(fun(fun(2))). fun(2) imprime “2” y llama a fun(fun(fun(3))). Entonces, la secuencia de llamadas a la función se convierte en fun(fun(fun(fun(fun(3))))). fun(3) imprime «3» y devuelve 3 (tenga en cuenta que la cuenta no se incrementa y no se llaman más funciones como si la condición no fuera cierta para la cuenta 3). Entonces, la secuencia de llamada de función se reduce a fun(fun(fun(fun(3)))). fun(3) vuelve a imprimir «3» y devuelve 3. Así que la llamada a la función se reduce de nuevo a fun(fun(fun(3))) que vuelve a imprimir «3» y lo reduce a fun(fun(3)). Esto continúa y obtenemos “3” impreso 5 veces en la pantalla. 

Complejidad del tiempo: O(2 ⁿ )

Espacio Auxiliar : O(n)

Escriba comentarios si encuentra que alguna de las respuestas/códigos es incorrecta, o si desea compartir más información/preguntas sobre los temas discutidos anteriormente.