Recursive function calls


#1

i was doing some exercises outside codecademy and came across this code:

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)


print(is_odd(17))
print(is_even(23))

this is the explanation:

Recursion can also be indirect. One function can call a second, which calls the first, which calls the second, and so on. This can occur with any number of functions.

but i can't wrap my head around it, can someone explain why this code works?

i understand of course that there are far more efficient ways to determine if the number is even or odd (by using %), but i just want to understand recursive function calling each other

this is the code for the question:

def fib(x):
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)
print(fib(4))

but given i don't understand this, i have no idea how this could be 5.

could someone explain the example (odd/even) and/or the question?


5. Factoral
Factorial Question
Factorials - Why does this code actually work?
Functions Declartions? Confused?
Can anyone tell me why? Still confused
5. Factorial...I know the answer, just not WHY it's the answer
Practice Makes Perfect Factorial
#2

there are some explanations for fib in the comments on sololearn:

return fib(3)+fib(2)
for fib(2)
{return fib(1)+fib(0)
return (return 1 +return 1)
return (2)}
fib(2)=2
for fib(3)
{return fib(2)+fib(1)
return 2+1   #  fib(2)=2 ,fib(1)=1
return 3}
fib(3)=3
return 3+2 # fib(3)=3,fib(2)

and:

fib(4) = fib(3) + fib(2) = (fib(2) + fib(1)) + (fib(1) + fib(0)) = 
((fib(1) + fib(0)) + 1) + (1 + 1) = ((1+1)+1) + 2 = 3 + 2 => fib(4) =
 5

but i still don't understand, maybe it will help someone understand it


#3

When considering how recursion works, it is essential to know that more than one copy of the recursive function can be in the process of executing at the same time. For instance, if we have this factorial function, and function call ...

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(4))

... the invocation, factorial(4), will call factorial(3), and wait to receive back the return value. factorial(3) will make a call to factorial(2), and wait for its return value. factorial(2) will call factorial(1), which will call factorial(0). So, now we have several invocations of the function waiting to complete.

But, factorial(0), which is a base case, can resolve without an additional call. So, it returns its result to factorial(1), which can then resolve, and return its result to factorial(2), and so on up the line, until all invocations can resolve, and the final result can be printed.

Here's a fibonacci function from Stack Overflow: Recursion function in Python ...

def fibonacci(number):
    if number == 0: return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1) + fibonacci(number-2)

... and a diagram from another post in the same thread ...

The explanations offered in that thread are pretty good. The Fibonacci series recursion is more complicated than the factorial function, because each recursive invocation of the fibonacci function must wait for two calls to return, in order to complete its calculation.


TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'
Factorial
Recursive Factorial Function
#4

i will need some time to work through this, but in short in case of the factorial function, the function keeps calling until reaching the base case, and then it works "backwards" so to speak?

As always, your answers are of amazing quality given great insight and understanding


#5

Yes, each call gets stacked up, waiting for returned values to arrive from calls that it made, so that it can return its own value. The arrows in the Fibonacci diagram indicate how it proceeds. Arrows that point downward represent function calls. There are some sideways arrows because the recursive cases must make two calls in order to resolve. The upward arrows indicate that values are getting returned.

A diagram for factorial would be simpler, but similar, in principle.


#6

okay, i feel like i am beginning to understand. Thank you very much appylpye :slight_smile:


#7

Am I reading the call stack return sequence correctly? I think not...

print(is_odd(7))

is_odd returns   is_even returns


                                   True => return value
                                    ^
not is_even(7)   is_odd(6)        False 
                                    ^
not is_even(6)   is_odd(5)        True
                                    ^
not is_even(5)   is_odd(4)        False
                                    ^
not is_even(4)   is_odd(3)        True
                                    ^
not is_even(3)   is_odd(2)        False
                                    ^
not is_even(2)   is_odd(1)        True
                                    ^
not is_even(1)   is_odd(0)        False
                                    ^
not is_even(0)   True      => True //

#8

Hey mtf...

Nice effort to show the whole sequence. But What is the sequence of the call stack? The boolean values looks confusing.. could you explain how you got the return value of True? i still don't get the logic.


#9

Actually, that was my question, as well. If I understand it correctly, the call stack sequence is the calls on the left, It clears starting at the bottom True, working its way back up through each call, up to the top. The first call to come off returns True, the next, False, and so on up the stack.