linux - Bash 脚本 - 斐波那契

Question

我试图制作一个可以计算输入数字的斐波那契的递归函数，顺便说一句，我被困在如何获取递归获得的值上。

#!/bin/bash

#Function - Fibonacci
fib()
{

  number=$1

  if (( number < 2 ))
    then
      (( tmp = number ))
  else
      ((--number))
      term1=$(fib $number)

      ((--number))
      term2=$(fib $number)

      (( tmp = $(( term1 + term2 )) )) #Problem is here

  fi

  (( result = $result + tmp ))
  return $result

}

#Main Program.
fib $1
  echo fib $1 = $?

有人可以帮助我吗？

Answer 1

您的代码存在一些问题。您不能将 $? 用于任何有用的算术运算，因为数字在 255 处回绕。而且嵌入的 $((...)) 根本没有用——您已经在双括号内的算术上下文中。

#!/bin/bash

fib()
{
  local number term1 term2 # Avoid leaking to main scope
  number=$1
  if ((number < 2))
    then
      ((tmp=number))
  else
      ((--number))
      term1=$(fib "$number")
      ((--number))
      term2=$(fib "$number")
      ((tmp=term1+term2))
  fi
  ((result=result+tmp))
  printf '%s\n' "$result"
}

#Main Program.
fib "$1"   # Quote argument properly!

在 (( 算术括号 )) 中，变量前面不需要 $；它是无害的，但您可能应该尝试保持一致。

与任何简单的斐波那契实现一样，这是非常低效的。在辅助函数中计算一次序列的头部，然后拉出最终结果并显示它会更聪明。

#!/bin/bash

fib2() {
    local f
    ((f=$1+$2))
    printf '%i %i\n' "$f" "$1"
}

fib()
{
    local i j
    j=$1
    shift
    for((i=1; i<j; ++i)); do
        set -- $(fib2 ${1-1} ${2-0})
    done
    printf '%s\n' "${1-$i}"
}

#Main Program.
fib "$1"