递归算法问题.

Question

如果你的boss第一天给你一元钱，后面每一天给你的是前一天的一倍。 也就是说1，2，4，8.... 。现问到了30天后，你一共拿了多少钱？
要求： 用递归函数来实现

Answer 1

问题很简单，关键在于思路，下面是代码。

/*
·递归
  1. salarySum(n) = salarySum(n-1) + salary(n)
  2. salary(n) = 2 ^ (n-1)

·非递归
  循环
*/

function salary(nthDay){
  return Math.pow(2, nthDay-1)
}

// 递归
function salarySum(nthDay) {
  if (nthDay > 1) {
    return salarySum(nthDay - 1) + salary(nthDay)
  } else {
    return 1
  }
}

// 非递归
function salarySum(nthDay) {
  let day = 1
  let sum = 0
  while (day <= nthDay) {
    sum += salary(day)
    day++
  }
  return sum
}

Answer 2

PHP版本

function recursion($day){
    if($day == 1){
        return 1;
    }else{
        return recursion($day - 1) + pow(2,$day - 1);
    }
}
echo recursion(30);

Answer 3

哈哈，汗颜，看错题目

#不递归的实现方式
def fn(n):
    return 2 ** (n - 1)

#递归的实现方式
def fn1(n):
    return 1 if n <= 1 else fn1(n-1) * 2

Answer 4

#!/usr/bin/env python

def salary(n):
    '''Your salary everyday'''
    if n <= 1:
        return 1
    return 2*salary(n-1)


def money(n):
    '''Total money you get for n days.'''
    if n <= 0:
        return 0
    s = salary(n)  # or s = 2**(n-1)
    m = money(n-1)
    print("day %d: salary[%d] total[%d]" % (n, s, (s+m)))
    return s+m 

money(30)

day 1: salary[1] total[1]
day 2: salary[2] total[3]
day 3: salary[4] total[7]
day 4: salary[8] total[15]
day 5: salary[16] total[31]
day 6: salary[32] total[63]
day 7: salary[64] total[127]
day 8: salary[128] total[255]
day 9: salary[256] total[511]
day 10: salary[512] total[1023]
day 11: salary[1024] total[2047]
day 12: salary[2048] total[4095]
day 13: salary[4096] total[8191]
day 14: salary[8192] total[16383]
day 15: salary[16384] total[32767]
day 16: salary[32768] total[65535]
day 17: salary[65536] total[131071]
day 18: salary[131072] total[262143]
day 19: salary[262144] total[524287]
day 20: salary[524288] total[1048575]
day 21: salary[1048576] total[2097151]
day 22: salary[2097152] total[4194303]
day 23: salary[4194304] total[8388607]
day 24: salary[8388608] total[16777215]
day 25: salary[16777216] total[33554431]
day 26: salary[33554432] total[67108863]
day 27: salary[67108864] total[134217727]
day 28: salary[134217728] total[268435455]
day 29: salary[268435456] total[536870911]
day 30: salary[536870912] total[1073741823]

Answer 5

我的思路是：先算出当前的金额，然后把今天的日期和金额传递下去，直到计算满30天为止。

function total(all, day,money){
    var day = day || 1,
        money = money || 0.5;

    money *= 2;
    // console.log( 'day'+day+': '+ money ); // 输出当前的金额
    day++;
    if(day<=all){
        return money + total(all, day, money);
    }
    return money;
}

然后调用total()即可：

total(1); // 1
total(2); // 3
total(7); // 127
total(30); // 1073741823