فصل 24- توابع

‎24.3‎- بازگشت بدون متغیرهای محلی

یک تابع حتی می‌تواند بدون استفاده از متغیرهای محلی، خودش را به طور بازگشتی فراخوانی نماید.

مثال ‎24-16‎. رشته فیبوناچی

#!/bin/bash
# fibo.sh   : رشته فیبوناچی (بازگشت)
# M. Cooper : مولف
# GPL3      : مجوز

# ----------الگوریتم--------------
# Fibo(0) = 0
# Fibo(1) = 1
#       وگرنه
#  Fibo(j) = Fibo(j-1) + Fibo(j-2)
# ---------------------------------
MAXTERM=15       #              تعداد جمله‌ها ‎(+1)‎ برای تولید شدن.
MINIDX=2         # اگر ‎idx‎ کوچکتر از ‎2‎ است، آنوقت ‎Fibo(idx) = idx‎

Fibonacci ()
{
  idx=$1         #             نیاز نیست محلی باشد. چرا لازم نیست؟
  if [ "$idx" -lt "$MINIDX" ]
  then
    echo "$idx"  #   دو جمله اول ‎0‎ و ‎1‎ هستند ... بالاتر را ببینید.
  else
    (( --idx ))                 # j-1
    term1=$( Fibonacci $idx )   # Fibo(j-1)

    (( --idx ))                 # j-2
    term2=$( Fibonacci $idx )   # Fibo(j-2)

    echo $(( term1 + term2 ))
  fi
  # یک پیاده‌سازی نازیبا، سرهم‌بندی ناخوش‌آیند.
  # پیاده‌سازی برازنده‌تر بازگشت فیبو در ‎C‎، یک
  #+ ترجمه سر راست الگوریتم سطر ‎7 تا ‎10‎ است.
}

for i in $(seq 0 $MAXTERM)
do              # محاسبه جمله‌های ‎$MAXTERM+1‎.
  FIBO=$(Fibonacci $i)
  echo -n "$FIBO "
done
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
#زمان می‌برد، چنین نیست؟ بازگشت در اسکریپت  کند است.
echo
exit 0

مثال ‎24-17‎. برج‌های هانوی

#! /bin/bash
#برج‌های هانوی
#‎Bash‎ اسکریپت
#‎Copyright (C) 2000 Amit Singh. ‎ تمام حقوق محفوظ است.
# http://hanoi.kernelthread.com
#تحت ‎Bash‎ نگارش ‎2.05b.0(13)-release‎ تست گردیده است.
#           همچنین در ‎Bash‎ نگارش ‎3.x‎ نیز کار می‌کند.
#
#   در «راهنمای اسکریپت‌نویسی پیشرفته ‎Bash‎‏» با اجازه
#+  از نویسنده اسکریپت به کار رفته است. توسط نگارنده
#     این سند اندکی ویرایش و توضیح‌گذاری گردیده است.
#=================================================================#
#  برج هانوی یک معمای ریاضی منتسب به ریاضیدان فرانسوی قرن
#+                       نوزدهم به نام ‎Edouard Lucas‎ است.
#
#                    در یک پایه، سه میله عمودی وجود دارد.
#      میله اول دارای حلقه‌های گرد  به ترتیب چیده شده است.
#  این حلقه‌ها، دیسک‌هایی با یک سوراخ در مرکز هستند، چنانکه
#+     می‌توانند روی میله ها جابه جا شده و یکنواخت بمانند.
# حلقه‌ها دارای قطرهای متفاوتی هستند، و مطابق اندازه‌شان به
# +               ترتیبی مخروطی شکل روی هم قرار گرفته‌اند.
#     کوچکترین حلقه در بالا، و بزرگترین حلقه در پایین است.
#
# کار محول شده، انتقال مجموعه حلقه‌ها به یک میله‌ دیگر است.
#هر نوبت فقط می‌توانید یک حلقه را به میله دیگر جابجا کنید.
# شما اجازه دارید حلقه‌ها را به میله اولیه‌شان برگشت بدهید.
#  می‌توانید حلقه کوچکتر را روی یک حلقه بزرگتر قرار بدهید،
#+                             اما برعکس آن را نمی‌توانید.
#دوباره، قرار دادن حلقه بزرگتر روی حلقه کوچکتر ممنوع است.
#
#   برای یک تعداد اندک از حلقه‌ها، فقط چند حرکت لازم می‌شود.
#+برای هر حلقه اضافی، حرکت‌های لازم، تقریبا دو برابر می‌شود،
#+         و «طراحی نقشه» به طور فزاینده‌ای پیچیده می‌گردد.
#     برای اطلاعات بیشتر، ‎http://hanoi.kernelthread.com‎ یا صفحه‌های
#+‎186-92‎ از ‎_The Armchair Universe_‎ نوشته ‎A.K. Dewdney‎ را ببینید.

#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#             شماره ‎3‎                شماره ‎2‎              شماره ‎1‎
#=================================================================#

E_NOPARAM=66  #        پارامتری به اسکریپت داده نشده.
E_BADPARAM=67 #تعداد پارامترهای اسکریپت غیر مجاز است.
Moves=        #  متغیر سراسری نگهدارنده تعداد حرکت‌ها.
dohanoi() {                  #           تابع بازگشت.
    case $1 in
    0)
        ;;
    *)
        dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
        ((Moves++))          
        dohanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
    1) case $(($1>0)) in                 #باید حداقل یک دیسک داشته باشیم.
       1)                                #           عبارت ‎case‎ تو در تو.
           dohanoi $1 1 3 2
           echo "Total moves = $Moves"   #   ‎2^n - 1‎ که ‎n‎ تعداد دیسک است.
           exit 0;
           ;;
       *)
           echo "$0: illegal value for number of disks";
           exit $E_BADPARAM;
           ;;
       esac
    ;;
    *)
       echo "usage: $0 N"
       echo "       Where \"N\" is the number of disks."
       exit $E_NOPARAM;
       ;;
esac
#                            تمرین‌ها:
#                   ----------------------------
# ‎(1‎ آیا فرمان‌های آنسوی این محل اصلاً می‌توانند اجرا شوند؟
#                                    چرا نه؟ (آسان)
#            ‎(2‎ عملکردهای تابع «dohanoi» را تشریح کنید.
#                (دشوار -- مرجع ‎Dewdney‎ فوق را ببینید.)