Función de potencia recursiva: enfoque

2 minutos de lectura

avatar de usuario
MOSFET

Estoy programando desde hace un tiempo (principiante), y las funciones recursivas son un concepto un tanto abstracto para mí. No diría que estoy atascado, el programa funciona bien, solo me pregunto si la función en sí podría escribirse sin la función pow en el código (pero aún así hacer exactamente lo que sugiere el problema)

Problema:
http://prntscr.com/30hxg9

Mi solución:

#include<stdio.h>
#include<math.h>

int power(int, int);

int main(void)
{
    int x, n;
    printf("Enter a number and power you wish to raise it to: ");
    scanf_s("%d %d", &x, &n);
    printf("Result: %d\n", power(n, x));
    return 0;
}

int power(int x, int n)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow(power(x, n / 2), 2);
    else return x * power(x, n - 1);
}

He intentado hacer esto: power(power(x, n – 1), 2); pero la ejecución falló, y todavía estoy retrocediendo por qué.

El código:

int power(int x, int n)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return power(power(x, n / 2), 2);
    else return x * power(x, n - 1);
}

no funciona porque cuando n es par, la potencia se llama con n = 2, que es par, y luego la potencia se llama con n = 2, que es par, y luego la potencia se llama con n = 2 … hasta que … ¡desbordamiento de pila!

Solución simple:

int power(int x, int n)
{
    if (n == 0) return 1;
    if (n % 2 == 0) {
        if (n == 2) return x * x;
        return power(power(x, n / 2), 2);
    }
    else return x * power(x, n - 1);
}

Para la función de potencia (digamos, x elevado a la n-ésima potencia) tienes dos casos:

exponent=0
exponent=n

Para el primer caso, solo necesita devolver 1. En el otro caso, debe devolver x a la potencia de n menos uno. Allí, solo usaste la función recursivamente.

int power(int x, n)
{
    if(n == 0) return 1;
    else return x * power(x, n-1);
}

  • Sí, pero el problema establece que el cálculo se puede hacer más rápido si lo abordamos como se describe

    – MOSFET

    13/03/2014 a las 20:50

avatar de usuario
vpb

double result = 1;
int count = 1;

public double power(double baseval, double exponent) {
  if (count <= Math.Abs(exponent)){
    count++;
    result *= exponent<0 ?1/baseval:baseval;
    power(baseval, exponent);
  }
  return result;
}

Esto funciona con valor positivo, negativo y 0

  • Sí, pero el problema establece que el cálculo se puede hacer más rápido si lo abordamos como se describe

    – MOSFET

    13/03/2014 a las 20:50

Simple pero hace n número de multiplicaciones. Los ejemplos anteriores son más eficientes porque agrupan dos operaciones en una iteración

int power(int x, int n)
{
    if (n == 0) return 1;

    return x * power(x, n-1);
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad