Умножение на силы с помощью рекурсии

Question

Я ищу способ кодировать программу, которая будет умножать целое число на показатель степени, используя только рекурсивный цикл.У меня очень ограниченное понимание рекурсии, но я смог написать что-то для факториала:

int fac2(int n)
{
    if (n == 1){
        return 1;
    } else {
        return n*fac2(n-1);
    }
}

У меня уже есть способ найти источник питания, но он использует цикл for:

int my_power(int x, int e)
{
    int i, total;
    total = 1;
    for (i = 1; i <= e; i++){
    total *= x;
    }
    return total;
}

Как я могу заменить это для цикла с помощью рекурсии?

Answer 1

int my_power (int x, int e) {
  if (e == 0) return 1;

  return x * my_power(x, e-1);
}

Answer 2

Используйте Дейва Андерсона в качестве основы, но также рассмотрите особые случаи, где:

1) x is 0 
2) e is negative.

Опять же, нет кода, поэтому вы можете попытаться выяснить это самостоятельно: -)

Обновление: Убедитесь, что вы создали несколько контрольных примеров и убедитесь, что все работают так, как вы думаете.После того, как тесты пройдут, вы узнаете, что ваша рекурсивная функция мощности работает правильно.

Пример: Если бы у вас было время, чтобы выяснить это самостоятельно, я бы предложил решение,с тестами:

int main(void)
{
    // n = 0 special case
    test(0, 0, 1);
    test(4, 0, 1);
    test(-5, 0, 1);

    // x = 0 special case
    test(0, 0, 1);
    test(0, 2, 0);

    // normal use
    test(4, 1, 4);
    test(4, -1, 0.25);
    test(-4, 3, -64);
    test(8, 2, 64);
    test(2, 3, 8);
    test(2, -3, 0.125);
    test(2, -5, 0.03125);

    // Invalid input tests
    std::cout << std::endl << "Invalid input tests" << std::endl;
    test (0, -2, NULL);
    test(0, -4, NULL);


    // Negative Tests
    std::cout << std::endl << "Negative tests (expect failure)" << std::endl;
    test(4, 0, 4);
    test(2, 1, 1);
    test(2, -5, 0.0313);

    return 0;
}

double power(int x, int n)
{
    // check for invalid input
    if (n == 0)
    {
        return 1;
    }

    if (n > 0)
    {
        return x * power(x, n - 1);
    }
    else if (n < 0)
    {
        return 1 / (x * power(x, -n - 1));
    }
}

bool test(int x, int n, double expected)
{
    if (x == 0 && n < 0)
    {
        std::cout << "Testing " << x << "^" << n << ", result = 'Invalid input'." <<  std::endl;
        return false;
    }

    double result = power(x, n);
    std::cout << "Testing " << x << "^" << n << ", result = " << result << ". Expected " << expected << " - test " << ((result == expected) ? "PASSED" : "FAILED") <<  std::endl;
    return true;
}

Вывод:

Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 4^0, result = 1. Expected 1 - test PASSED
Testing -5^0, result = 1. Expected 1 - test PASSED
Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 0^2, result = 0. Expected 0 - test PASSED
Testing 4^1, result = 4. Expected 4 - test PASSED
Testing 4^-1, result = 0.25. Expected 0.25 - test PASSED
Testing -4^3, result = -64. Expected -64 - test PASSED
Testing 8^2, result = 64. Expected 64 - test PASSED
Testing 2^3, result = 8. Expected 8 - test PASSED
Testing 2^-3, result = 0.125. Expected 0.125 - test PASSED
Testing 2^-5, result = 0.03125. Expected 0.03125 - test PASSED

Invalid input tests
Testing 0^-2, result = 'Invalid input'.
Testing 0^-4, result = 'Invalid input'.

Negative tests (expect failure)
Testing 4^0, result = 1. Expected 4 - test FAILED
Testing 2^1, result = 2. Expected 1 - test FAILED
Testing 2^-5, result = 0.03125. Expected 0.0313 - test FAILED

Answer 3

Помните, что рекурсивная функция вызывает себя, пока не будет достигнут некоторый базовый случай. Каков ваш базовый случай здесь? Возведение числа в степень - это то, что вы любите говорить, что вы умножите некоторое число на количество раз. Подсказка - вызывать рекурсивную функцию, уменьшая мощность на единицу, пока вы не достигнете желаемого базового варианта.

Answer 4

Правильный способ сделать то, что вы хотите, это заметить, что:

• x ⁿ = (x ^{n / 2} ) ², если n четное
• x ⁿ = x * (x ^{/n / 2⫞} ) ² , если n равнонечетное
• x ¹ = x
• x ⁰ = 1

где "⊦n / 2⫞"означает целую часть n / 2 (то, что n / 2 дает вам в C, когда n - целочисленная переменная).

В отличие от факториала, который читает

• n!= n * (n - 1) !, если n> 0
• 0!= 1

у вас должна быть возможность написать рекурсивную программу для возведения в степень, основанную на факториале.

Answer 5

Существует способ думать об этом, который требует, чтобы мы вышли за пределы C-land, но это так просто в своем сердце и мощно, что его стоит рассмотреть.

Рекурсия и итерация не так отличаются, как онисначала кажется.На определенном уровне на самом деле их трудно отличить.Мы не будем подробно останавливаться на этом, но рассмотрим рекурсивную реализацию цикла for (без языка):

for (i, n, f, a) = 
  if (i > n) {
    return a
  } else {
    return for (i+1, n, f, f(a, i))
  }

(Кстати, a называется "аккумулятором").", потому что он накапливает значение каждого" цикла ")

Единственное, что может быть для вас новым, это то, что выше обрабатывает функции как любой другой тип данных, который называется" first-функции класса".Обычно это не то, что вы делаете в C (вы можете сделать это ограниченным образом, передавая указатели на функции), но это настолько мощная концепция, что ее стоит изучить.

Используя приведенное выше определение for, мы напишем вашу факториальную функцию следующим образом:

mult(a,b) = a*b
fac(n) = for (1, n, mult, 1)

Это вычисляет, умножая каждый i на аккумулятор.

Другая мощная концепция (которую, к сожалению, C вообще не поддерживает) - это анонимные функции, которые просто являются функциями, созданными без имен.Я собираюсь использовать синтаксис e -> ... для анонимных функций, где ... - некоторое выражение (например, x -> x+1), а (a,b) - для пары переменных.В C анонимные функции могут показаться бесполезными, но если вы можете передавать функции так же легко, как вы можете передавать числа, вы можете упростить fac до одной строки:

fac(n) = for (1, n, (a,i) -> a*i, 1)

pow может бытьзаписывается как:

pow(x, e) = for(1, e, (a,i) -> a*x, 1) 

Разверните в этом for, и вы получите рекурсивное определение для pow.

Хотя это дает вам рекурсивную функцию, есть другая реализация(Александр на самом деле), это более эффективный по времени.

Answer 6

Насколько мне известно, эта функция будет работать в любом вероятном случае (кто-то, задавший "asdfj" как x или e, скорее всего).

#include <stdio.h>

double my_power(int x, int e)
{
    if (x == 0)
    {
        return 0;
    }
    if (e == 0)
    {
        return 1;
    }
    if (e > 0)
    {
        return x * my_power(x, e-1);
    }
    if (e < 0)
    {
        return 1/(x*my_power(x, -e-1));
    }
}

Answer 7

Вот вам псевдокод:

FUNCTION mypower(number, exponent)
    IF exponent == 0 THEN:
        RETURN 1
    ELSE IF exponent > 0 THEN:
        RETURN number * mypower(number, exponent - 1)
    ELSE:
        RETURN 1 / mypower(number, -(exponent))

И, о, возвращаемое значение должно быть double.

Вот фактический код:

double mypower(int n, int e) {
    if (e == 0)
        return 1;
    else if (e > 0)
        return n * mypower(n, e - 1);
    else
        return 1 / mypower(n, -e);
}