函数题：汉诺塔数列(递归版)

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, ...

第 1 项为 1，表明移动 1 片圆盘的汉诺塔需 1 步；第 2 项为 3，表明移动 2 片圆盘的汉诺塔需 3 步；……，以此类推。请编写递归函数，求汉诺塔数列中任一项的值。

#### 函数原型

c
double NumHanoi(int index);


说明：参数 index 为索引号(正整数)，函数值为汉诺塔数列第 index 项的值。

要求：不要使用循环语句。不要调用 pow、exp 等数学函数。

#### 裁判程序

c
#include <stdio.h>

double NumHanoi(int index);

int main()
{
int n;
scanf("%d", &n);
printf("%.15g\n", NumHanoi(n));
return 0;
}

/* 你提交的代码将被嵌在这里 */


#### 输入样例1
in
3


#### 输出样例1
out
7



#### 输入样例2
in
45


#### 输出样例2
out
35184372088831








答案：若无答案欢迎评论