Bash 脚本 - 斐波那契

Question

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

#!/bin/bash

#Function - Fibonacci
fib()
{

  number=

  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 
  echo fib  = $?

有人可以帮助我吗？

Answer 1

试试这个方法：

fn() {
    echo 'returnValue';
}

echo `fn`;

Answer 2

我相信你知道 "coding FIBONACCI with recursion is NOT a good idea"。

递归 Fib() -> O(2^n)
迭代 Fib() -> O(n)

请参考this youtube video。

Answer 3

I got stuck on how to get the values obtained by the recursion.

您已经在脚本的最后一行中添加了它 - $?。只需在 fib 中执行相同操作 - 替换

      term1=$(fib $number)
      …
      term2=$(fib $number)

和

      fib $number; term1=$?
      …
      fib $number; term2=$?

仍然是你的脚本 returns 奇怪的值，但你肯定可以从这里恢复。（set -x 可能会有帮助。）

Answer 4

我运行你的代码，我看到当数字小于 2 时，数字不会被 returned。它不断递减值并继续寻找负数的斐波那契.这可能就是它给出 st运行ge 结果的原因（这是在应用 Armali 给出的修复之后）。

我不确定这些算术运算的语法是否正确，正如您在添加方法结果的行中所指出的那样。

查看此 link，它显示了 bash 中的递归函数，但它打印的是值而不是 return。 http://tldp.org/LDP/abs/html/recurnolocvar.html

我的理解是，在 bash 递归脚本中处理局部变量的方式存在一些问题。我看到当函数在第二次递减后第二次调用时，第一次调用的 return 值覆盖了原始数值，导致负数，因此 st运行ge 结果。必须有一些其他方法来处理递归调用中的 return 值。

Answer 5

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

#!/bin/bash

fib()
{
  local number term1 term2 # Avoid leaking to main scope
  number=
  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 ""   # Quote argument properly!

在((算术括号内))不需要变量前面的$；它是无害的，但你应该尽量保持一致。

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

#!/bin/bash

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

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

#Main Program.
fib ""

Answer 6

Re tripleee 的回答：这可以更快地完成。

我认为辅助函数调用真的很昂贵。下面的版本在 2.344 秒时计算出 fib 100000，而辅助函数版本在 1 分 28.44 秒时执行相同的操作。虽然，您只能得到正确的斐波纳契数，直到 92 斐波那契，但对我来说，在 93 斐波那契时，您已经达到了 intmax_t 设置。

fibnorec(){
    # typecheck                                                                                           
    if [[ ! "" =~ ^[0-9]+$ ]]
    then
        return 1
    fi

    # make arg into int                                                                                   
    declare -i n=""

    # Return fibonacci number at index n...                                                               
    if [[ $n -le 1 ]]
    then
        # index 0 and index 1 are numbers 0 and 1 respectively.
        printf '%s\n' $n;
    fi
    # For index 2 and up (position 3 and up)
    declare -i sum=1;
    declare -i prev=1;
    for ((i=2; i<n; i++))
    do
        declare -i save=$sum;
        sum+=$prev;
        prev=$save;
    done
    printf '%s\n' $sum
}
time fibnorec 100000

Bash 脚本 - 斐波那契

Bash Script - Fibonacci

linux

bash

shell

fibonacci