Вывести ряд Фибоначчи с использованием рекурсии в bash только с одной переменной - PullRequest
Новая
       19

Вывести ряд Фибоначчи с использованием рекурсии в bash только с одной переменной

0 голосов
/ 26 февраля 2019

Я хотел бы знать, как напечатать ряд Фибоначчи, используя рекурсию в bash только с одной переменной.

Из того, что я сделал: 

fib()
    {
    i=$1
    if (( $i <= 1 ))
    then echo 0
    elif (( $i == 2 ))
    then echo 1
    else

    echo $(( $(fib $(($i - 1)) ) + $(fib $(($i - 2)) ) ))

fi
 }

echo $(fib $1)

Я получаю правильный выводиз последней итерации, например, если я введу 10, я получу 34, но я бы хотел напечатать всю последовательность чисел, т.е. все итерации.Как мне этого добиться?

Другой способ, которым я пытался, был: 

#!/bin/bash
arr[0]=0
arr[1]=1

for (( i=0; i<=10; i++ ))
do
    echo -n "${arr[0]} "
    arr[0]=$((${arr[0]} + ${arr[1]} ))
    arr[1]=$((${arr[0]} - ${arr[1]} ))
done
echo ""

Но, очевидно, здесь я использовал цикл for, но я не хочу использовать другую переменную.

Ответы [ 3 ]

0 голосов
/ 26 февраля 2019

Если вы хотите напечатать каждое значение Фибоначчи от 1 до $ n, я предлагаю: 

fib_r() {
    local i=$1
    if (( i < 0 )); then
        echo "Error: negative numbers not allowed" >&2
        exit 1

    elif (( i <= 1 )); then
        echo $i

    else
        echo $(( $($FUNCNAME $((i - 1)) ) + $($FUNCNAME $((i - 2)) ) ))
    fi
}

fib() {
    local i
    for (( i = 1; i <= $1; i++ )); do
        fib_r $i
    done
}

fib 10

вывод 

0
1
1
2
3
5
8
13
21
34

Это по-прежнему одна переменная, хотя по одной на функцию.

Я использую переменную bash $ FUNCNAME в рекурсивной функции, чтобы вам не приходилось жестко кодировать имя функции внутри себя.Я получил немного, не обновив эту строку, когда переименовал функцию.

Конечно, ваша производительность значительно улучшится, если вы кешируете результаты: "fib 16" занимает у меняВМ, около 3,5 с без кэширования и около 0,03 с без кэширования. 

fib_r() {
    local i=$1
    if (( i < 0 )); then
        echo "Error: negative numbers not allowed" >&2
        exit 1

    elif [[ -n ${fib_cache[i]} ]]; then
        echo "${fib_cache[i]}"

    elif (( i <= 1 )); then
        echo $i

    else
        echo $(( $( $FUNCNAME $((i - 1)) ) + $( $FUNCNAME $((i - 2)) ) ))
    fi
}

fib_cache=()

fib() {
    local i
    for ((i=1; i<=$1; i++)); do
        fib_cache[i]=$(fib_r $i)
        echo "${fib_cache[i]}"
    done
}
0 голосов
/ 26 февраля 2019

Просто для (моего рода) удовольствия, этот код печатает числа Фибоначчи от 0-го до 92-го (как определено в число Фибоначчи - Википедия ) с рекурсивной функцией, которая не использует переменных: 

#! /bin/bash

function fib
{
    echo ${3-0}

    (($1 > 0)) && fib $(($1-1)) ${3-0} $((${2-1}+${3-0}))
}

fib 92

Некоторые могут утверждать, что использование позиционных параметров ($1, $2, $3) для этого - обман, но тогда можно сказать, что другие решения используют две переменные ($i и$1).

Код запускается на моей (старой) Linux-машине менее чем за 0,01 секунды.

Код должен работать с номерами до 92 с версией 3 Bash или более поздней на любомПлатформа.См. Предел числа Bash? .Числа, превышающие 93, приведут к тому, что код выдаст результаты мусора из-за арифметического переполнения.

0 голосов
/ 26 февраля 2019

Переменные в bash являются глобальными по умолчанию.Вам нужно явно указать i local. 

 fib () {
     local i
     i=$1
     if (( i <= 1 )); then
         echo $i
     else
         echo $(( $(fib $((i-1)) ) + $(fib $((i - 2)) ) ))
     fi
}

(Кроме того, ваши базовые случаи немного отличаются, если вы начинаете с 0, а 2 не обязательно должно быть базовым; fib 2 может бытьвыведено из базовых случаев fib 0 и fib 1.)

...