歪歪大陆
0%

递归函数

Posted on In ,

递归函数

递归函数，简单说就是函数调用自己。

复习简单函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[root@vm-101 ~]# cat r.sh
#!/bin/bash

function plus(){
    sum=0

    for ((i=$1; i>0; i--))
    do
        sum=$[ $sum + $i ]
    done

    return 0
}


plus $1

echo "sum : $sum"

exit 0


[root@vm-101 ~]# bash r.sh 100
sum : 5050

用递归函数改造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[root@vm-101 ~]# cat r.sh
#!/bin/bash

function plus(){
    if [ $1 -gt 0 ];then
        sum=$[ $sum + $1 ]
        plus $[ $1 - 1 ]
    fi

    return 0
}

sum=0

plus $1

echo "sum : $sum"

exit 0



[root@vm-101 ~]# bash r.sh 100
sum : 5050

汉洛塔

汉洛塔是一个非常经典的，需要用到递归思想解决的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
[root@vm-101 ~]# cat hanluota.sh
#!/bin/bash

# 注释是个好习惯

function mv() {
    echo "invoke : mv $@"
    if [ $1 -eq "1" ];then
        echo  "$2 -> $4 : $@"
    else
        mv $[$1-1] $2 $4 $3
        echo  "$2 -> $4 : mv $[$1-1] $2 $4 $3 : mv $[$1-1] $3 $2 $4"
        mv $[$1-1] $3 $2 $4
    fi
}

# 层数 起始位 缓冲区 目的地
mv ${1:-3} A B C

exit 0

[root@vm-101 ~]# bash hanluota.sh
invoke : mv 3 A B C
invoke : mv 2 A C B
invoke : mv 1 A B C
 A -> C : 1 A B C
 A -> B : mv 1 A B C : mv 1 C A B
invoke : mv 1 C A B
 C -> B : 1 C A B
 A -> C : mv 2 A C B : mv 2 B A C
invoke : mv 2 B A C
invoke : mv 1 B C A
 B -> A : 1 B C A
 B -> C : mv 1 B C A : mv 1 A B C
invoke : mv 1 A B C
 A -> C : 1 A B C