I understand recursive functions with only one nested function, such as this one:
def recurseInfinitely( n ):
try:
recurseInfinitely(n+1)
except RuntimeError:
print("We got to level %s before hitting the recursion limit." % n)
This function calls itself until hits the barrier, which is 998 times.
But when a function calls itself for two times, things get really confusing for me.
This question is inspired from a video on youtube which explains recursion and solves a problem called Tower of Hanoi via using Python.
Recursion 'Super Power' (in Python) - Computerphile
I changed the functions to these:
def move(x, y, name):
print(" {} Move from {} to {}".format(name, x,y))
def hanoi(n_of_disks,from_position,helper_position,target_position, name):
if n_of_disks==0:
print("#name: %s do nothing if there's no disk: %d" % (name, n_of_disks))
pass
else:
# --> A
print("Before A, name: %s disk: %d" % (name, n_of_disks))
hanoi(n_of_disks-1, # 3
from_position, # A
target_position, # C
helper_position, # B
name='FIRST RECURSOR')
move(from_position, # A
target_position, # C
name)
# --> B
print("Before B, name: %s disk: %d" % (name, n_of_disks))
hanoi(n_of_disks-1, # 3
helper_position, # B
from_position, # A
target_position, # C
name='SECOND RECURSOR')
And ran it...
hanoi(n_of_disks=4,
from_position='A',
helper_position='B',
target_position='C',
name="START THE SHOW")
The result is:
Before A, name: START THE SHOW disk left: 4
Before A, name: FIRST RECURSOR disk left: 3
Before A, name: FIRST RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from A to C
Before B, name: FIRST RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 3
Before A, name: SECOND RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from C to A
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from C to B
Before B, name: SECOND RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from A to B
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
START THE SHOW Move from A to C
Before B, name: START THE SHOW disk left: 4
Before A, name: SECOND RECURSOR disk left: 3
Before A, name: FIRST RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from B to C
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from B to A
Before B, name: FIRST RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from C to A
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 3
Before A, name: SECOND RECURSOR disk left: 2
Before A, name: FIRST RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
FIRST RECURSOR Move from A to B
Before B, name: FIRST RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from A to C
Before B, name: SECOND RECURSOR disk left: 2
Before A, name: SECOND RECURSOR disk left: 1
#name: FIRST RECURSOR do nothing if there's no disk: 0
SECOND RECURSOR Move from B to C
Before B, name: SECOND RECURSOR disk left: 1
#name: SECOND RECURSOR do nothing if there's no disk: 0
Some Questions:
Is recursion really something useful in real life? From what I've read, it is:
I'm not sure to understand the purpose of this code, but I do understand recursion.
As you wrote it, the function recurseInfinitely is a terminal recursive function. Which means that the recursive call is the very last operation to be done in the function. Therefore the execution of such function is linear :
recurseInfinitely(0)
└─ recurseInfinitely(1)
└─ recurseInfinitely(2)
└─ ...
At the opposite, the function hanoi is not terminal recursive since it calls twice itself. The execution looks like a binary tree. For example with n = 3 :
hanoi(3,A,B,C) 3
├─ hanoi(2,A,C,B) 2
│ ├─ hanoi(1,A,B,C) 1
│ │ ├─ hanoi(0,A,C,B) 0
│ │ └─ hanoi(0,C,A,B) 0
│ └─ hanoi(1,C,A,B) 1
│ ├─ hanoi(0,C,B,A) 0
│ └─ hanoi(0,A,C,B) 0
└─ hanoi(2,B,A,C) 2
├─ hanoi(1,B,C,A) 1
│ ├─ hanoi(0,B,A,C) 0
│ └─ hanoi(0,C,B,A) 0
└─ hanoi(1,A,B,C) 1
├─ hanoi(0,A,C,B) 0
└─ hanoi(0,B,A,C) 0
which corresponds to you results.
In practice, such algorithm is to avoid since it grows exponentially with n (~2^n).
Concerning the usefulness of recursion, it is not true that recursion is more resource expensive or slower. However, what is true is that recursion isn't suited for all languages. In fact, some languages are entirely based on recursion (for example Lisp, Scheme and SQL). It is called functional programming and is, indeed, very elegant.
For example, in Scheme the factorial function could be written
(define (fact n)
(if (zero? n)
1
(* n (fact (- n 1)))
)
)
One should note that this function is not terminal recursive since it does a multiplication after the recursive call.
A terminal version (using an accumulator) of it would be
(define (fact n)
(fact-acc n 1)
)
(define (fact-acc n acc)
(if (zero? n)
acc
(fact-acc (- n 1) (* n acc))
)
)