编写一个函数实现n^k（n的k次方），使用递归实现。

好的，以下是一个使用递归实现n^k的函数：

def power(n, k):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return power(n * n, k // 2)
    else:
        return n * power(n, k - 1)

这个函数在计算n^k时，使用了一个分治的思想。如果k为偶数，则可以将n^k拆分为(n^2)^(k/2)，可以递归计算(n^2)^(k/2)。如果k为奇数，则可以将n^k拆分为n * n^(k-1)，同样可以递归计算n^(k-1)。当k为0时，返回1，递归终止。

相关问题

用C语言编写一个函数实现n^k（n的k次方），使用递归实现。

好的，以下是一个使用递归实现n^k的C函数：

#include <stdio.h>

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

int main() {
    int n, k;
    printf("请输入底数n和指数k：");
    scanf("%d%d", &n, &k);
    printf("%d的%d次方是%d\n", n, k, power(n, k));
    return 0;
}

这个函数与之前提供的Python版本的函数非常相似。当k为0时，返回1，递归终止。如果k为偶数，则可以将n^k拆分为(n^2)^(k/2)，可以递归计算(n^2)^(k/2)。如果k为奇数，则可以将n^k拆分为n * n^(k-1)，同样可以递归计算n^(k-1)。

数据结构与算法中使用C语言编写，在VC++中运行，并在每行代码中加入注释 题目： 一、设有三个元素XYZ顺序进栈（进的过程中允许出栈），若出栈顺序为XZY，请用顺序栈实现这一过程。 二、设有三个元素XYZ顺序进栈（进的过程中允许出栈），若出栈顺序为YZX，请用链栈实现这一过程。 三、编写一个函数实现n^k（n的k次方），使用递归实现。

一、使用顺序栈实现XZY的出栈顺序：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;
} SqStack;

void initStack(SqStack *s) {
    s->top = -1;
}

int push(SqStack *s, int x) {
    if (s->top == MAXSIZE - 1) {
        return 0;
    }
    s->top++;
    s->data[s->top] = x;
    return 1;
}

int pop(SqStack *s, int *x) {
    if (s->top == -1) {
        return 0;
    }
    *x = s->data[s->top];
    s->top--;
    return 1;
}

int getTop(SqStack *s, int *x) {
    if (s->top == -1) {
        return 0;
    }
    *x = s->data[s->top];
    return 1;
}

int main() {
    SqStack s;
    int x, y, z;
    initStack(&s);
    push(&s, 1);  // X入栈
    push(&s, 2);  // Y入栈
    push(&s, 3);  // Z入栈
    pop(&s, &x);  // X出栈
    pop(&s, &z);  // Z出栈
    pop(&s, &y);  // Y出栈
    printf("%d %d %d\n", x, y, z);  // 输出X Y Z的出栈顺序
    return 0;
}

二、使用链栈实现YZX的出栈顺序：

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

void initStack(LinkList *s) {
    *s = NULL;
}

int push(LinkList *s, int x) {
    LNode *p = (LNode *) malloc(sizeof(LNode));
    p->data = x;
    p->next = *s;
    *s = p;
    return 1;
}

int pop(LinkList *s, int *x) {
    if (*s == NULL) {
        return 0;
    }
    *x = (*s)->data;
    LNode *p = *s;
    *s = (*s)->next;
    free(p);
    return 1;
}

int getTop(LinkList s, int *x) {
    if (s == NULL) {
        return 0;
    }
    *x = s->data;
    return 1;
}

int main() {
    LinkList s;
    int x, y, z;
    initStack(&s);
    push(&s, 1);  // X入栈
    push(&s, 2);  // Y入栈
    push(&s, 3);  // Z入栈
    pop(&s, &z);  // Z出栈
    pop(&s, &y);  // Y出栈
    pop(&s, &x);  // X出栈
    printf("%d %d %d\n", y, z, x);  // 输出Y Z X的出栈顺序
    return 0;
}

三、使用递归实现n^k：

#include <stdio.h>

double pow(int n, int k) {
    if (k == 0) {
        return 1;
    }
    double t = pow(n, k / 2);
    if (k % 2 == 0) {
        return t * t;
    } else {
        return t * t * n;
    }
}

int main() {
    int n = 2, k = 5;
    double ans = pow(n, k);
    printf("%d的%d次方为%.0lf", n, k, ans);
    return 0;
}