In need of recursion explanation-CodePudding

Found this code chunk on geeksforgeeks, can't seem to get a hang of it. Tried to write down the call stack on paper, still doesn't click for me.

The following algorithm supposed to check wheter integer num is palindrome or not

# A function that returns true
# only if num contains one digit
def oneDigit(num):
    
    # comparison operation is faster
    # than division operation. So
    # using following instead of
    # "return num / 10 == 0;"
    return ((num >= 0) and
            (num < 10))

# A recursive function to find
# out whether num is palindrome
# or not. Initially, dupNum
# contains address of a copy of num.
def isPalUtil(num, dupNum):
    
    # Base case (needed for recursion
    # termination): This statement
    # mainly compares the first digit
    # with the last digit
    if oneDigit(num):
        return (num == (dupNum[0]) % 10)

    # This is the key line in this
    # method. Note that all recursive
    # calls have a separate copy of
    # num, but they all share same
    # copy of *dupNum. We divide num
    # while moving up the recursion tree
    if not isPalUtil(num //10, dupNum):
        return False

    # The following statements are
    # executed when we move up the
    # recursion call tree
    dupNum[0] = dupNum[0] //10

    # At this point, if num
    # contains i'th digit from
    # beginning, then (*dupNum)
    # contains i'th digit from end
    return (num % 10 == (dupNum[0]) % 10)

# The main function that uses
# recursive function isPalUtil()
# to find out whether num is
# palindrome or not
def isPal(num):
    # If num is negative,
    # make it positive
    if (num < 0):
        num = (-num)

    # Create a separate copy of
    # num, so that modifications
    # made to address dupNum
    # don't change the input number.
    dupNum = [num] # *dupNum = num

    return isPalUtil(num, dupNum)

# Driver Code
n = 12321
if isPal(n):
    print("Yes")
else:
    print("No")

n = 12
if isPal(n) :
    print("Yes")
else:
    print("No")

n = 88
if isPal(n) :
    print("Yes")
else:
    print("No")

n = 8999
if isPal(n) :
    print("Yes")
else:
    print("No")

# This code is contributed by mits

How does the stack work in this scenario?

CodePudding user response：

The problem this code tries to solve is to get the first and last, the second and second to last... digits of a number.

We can get the digits of a number from the right one by one using the integer division and remainder operations. But getting the digits of a number from the left one by one is more problematic. Although, you could integer divide a number by 10^n where n is the number of digits that particular number has minus one. For example, say 999 integer_divide 100 equal 9. The number of digits in a number can be calculated using logarithms. This approach gives us a method to check whether a number is palindromic without using recursion or converting it to a string.

But back to the recursion problem. What the code does is that it has an immutable and a mutable copy of the number. Changes to the immutable copy are not reflected in other frames of the call stack while changes to the mutable copy are reflected in other frames.

Now, as we go down the recursive calls stack, we integer divide the immutable copy by 10 each time, up until we hit the base case which is when the immutable copy has only one digit. Note, that this one digit is the left most digit of the number.

Now, the function returns. As it comes back up the call stack, we take the remainder of the mutable copy by 10 (mutable_copy % 10). Note that this is the right most digit of the number. We compare the left most and right most. If they are not equal we return False. Otherwise we continue while also integer dividing the mutable copy by 10. This integer division has the effect that the mutable copy in the frame up the recursive stack has one digit less from the right. This sets the stage for the comparison of the corresponding digits in that frame.

Here I have edited the code a little bit so you can visualize what's happening:

# A function that returns true
# only if num contains one digit
def oneDigit(num):
    
    # comparison operation is faster
    # than division operation. So
    # using following instead of
    # "return num / 10 == 0;"
    return ((num >= 0) and
            (num < 10))

# A recursive function to find 
# out whether num is palindrome 
# or not. Initially, dupNum  
# contains address of a copy of num. 
def isPalUtil(num, dupNum, depth): 
     
    # Base case (needed for recursion 
    # termination): This statement 
    # mainly compares the first digit 
    # with the last digit 
    if oneDigit(num): 
        print("--"*depth   " "   "hit base case")  
        return (num == (dupNum[0]) % 10) 
 
    # This is the key line in this 
    # method. Note that all recursive 
    # calls have a separate copy of 
    # num, but they all share same 
    # copy of *dupNum. We divide num 
    # while moving up the recursion tree 
    print(f'{"--"*depth} We are at depth {depth}. Immutable: {num}, Mutable: {dupNum}') 
    if not isPalUtil(num //10, dupNum, depth 1): 
        return False 
 
    # The following statements are 
    # executed when we move up the  
    # recursion call tree 
    dupNum[0] = dupNum[0] //10 
    print(f'{"--"*depth} We are at depth {depth}, Immutable: {num}, Mutable: {dupNum}') 
    # At this point, if num  
    # contains i'th digit from 
    # beginning, then (*dupNum) 
    # contains i'th digit from end 
    return (num % 10 == (dupNum[0]) % 10) 
 
# The main function that uses 
# recursive function isPalUtil() 
# to find out whether num is  
# palindrome or not  
def isPal(num): 
    # If num is negative, 
    # make it positive 
    if (num < 0): 
        num = (-num)  
 
    # Create a separate copy of 
    # num, so that modifications 
    # made to address dupNum  
    # don't change the input number. 
    dupNum = [num] # *dupNum = num 
 
    return isPalUtil(num, dupNum, 1)

Running isPal(n) with the above produces the following:

-- We are at depth 1. Immutable: 123321, Mutable: [123321]
---- We are at depth 2. Immutable: 12332, Mutable: [123321]
------ We are at depth 3. Immutable: 1233, Mutable: [123321]
-------- We are at depth 4. Immutable: 123, Mutable: [123321]
---------- We are at depth 5. Immutable: 12, Mutable: [123321]
------------ hit base case
---------- We are at depth 5, Immutable: 12, Mutable: [12332]
-------- We are at depth 4, Immutable: 123, Mutable: [1233]
------ We are at depth 3, Immutable: 1233, Mutable: [123]
---- We are at depth 2, Immutable: 12332, Mutable: [12]
-- We are at depth 1, Immutable: 123321, Mutable: [1]

I suggest you further edit the code to make the output more clear to yourself.

On a side note, I really don't think that that code from GfG is educational by any means. The comments are lengthy and variable names unclear. Usage of * suggests that a C/C programmer has ported the code to python without proper care or maybe even knowledge. My experience is that GfG material is of low quality in comparison to other resources and the only reason people refer to it so much is that their links have good ranking in SER.