Python Forum
Execution of Another Recursive Function
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Execution of Another Recursive Function
#1
Greetings,

I want to make sure that I understand the execution of the following "simple" recursive function that basically takes a number and adds it to every number below it. This function will output the value of 10.


def get_recursive_sum(n):
    if n < 0:
        return -1
    elif n == 0:
        return 0
    else:
        return n + get_recursive_sum(n - 1)

print(get_recursive_sum(4))
I am going to make the following assumption here. Please correct me if I am wrong.

  1. 1. Each recursive call simply returns the value of n to each child recursive call. Basically the variable n will be overwritten by returning the sum of
    n = n + get_recursive_sum(n - 1)
    to each of the child calls until we get to zero. Recursion stops and the last value is returned to the initial caller which is the value of 10.

    2. Starting with the first call n = 4, 4 and subsequent values are added then overwritten by return values. As I stated above
    n = n + get_recursive_sum(n - 1)

Something like:
4 + get_recursive_sum(4 - 1) #returns 7 
                7 + get_recursive_sum(3 - 1) #returns 9
                   9 + get_recursive_sum(2 - 1) #returns 10
                      10 get_recursive_sum(1 - 1) #stops because n = 0
       #return 10 to initial caller.
Did I correctly describe the execution of this function?

Thanks,
Matt
Reply
#2
(Dec-03-2020, 05:07 PM)muzikman Wrote: 1. Each recursive call simply returns the value of n to each child recursive call.

You don't return to a child, you pass an argument to a child. The child returns a value to its parent.

Each instance of the function call has its own copy of the variables, so nothing is "overwritten" here. One call has n=5, the child has n=4, but the variables are separate.

Quote:Basically the variable n will be overwritten by returning the sum of
n = n + get_recursive_sum(n - 1)
to each of the child calls until we get to zero. Recursion stops and the last value is returned to the initial caller which is the value of 10.

No. Each child returns only to its parent.

Quote:2. Starting with the first call n = 4, 4 and subsequent values are added then overwritten by return values.

Nothing is overwritten. more like this...
4 + get_recursive_sum(4 - 1) #pause
                    get_recursive_sum(3 - 1) #pause
                       get_recursive_sum(2 - 1) #pause
                         get_recursive_sum(1 - 1) #returns 0
                       unpause.  calculate 0+1 and return 1
                    unpause.  calculate 2 + 1 and return 3
                  unpause.  calculate 3 + 3 and return 6
               gets the 6 from the child and calculates 4 + 6 as 10.
The addition can't happen until it knows the answer from the child. So each instance will pause and wait for the child to finish and come back. Then the answers return in reverse order, always from one child to it's immediate parent.
snippsat likes this post
Reply
#3
This one is too easy.
def rsum(n):
    if n > 0:
        return n + rsum(n-1)
    elif n < 0:
        return n + rsum(n+1)
    return 0
print(rsum(5))
rsum(5) = 5 + rsum(4) <- Start of recursion
rsum(4) = 4 + rsum(3)
rsum(3) = 3 + rsum(2)
rsum(2) = 2 + rsum(1)
rsum(1) = 1 + rsum(0)
rsum(0) = 0 <- End of recursion, Unwinding from here
rsum(0) returns 0
rsum(1) returns 1
rsum(2) returns 3
rsum(3) returns 6
rsum(4) returns 10
rsum(5) returns 15 <- Value returned by original call
15 <- output of print(rsum(5))

From the first call of rsum(5) we begin adding recursive rsum() calls to the call stack. When rsum(0) returns 0 that is the end of the recursion and we begin completing the functions and removing them from the call stack. As Bowlofred says, there is no overwriting of anything. When you call a function the current context is saved to the call stack and the program starts executing the new function. When the function completes the previous context is restored and that context continues execution from the place where it was paused. This is exactly the same thing that happens when you call any function. The only thing special about recursion is the calling function and called function have the same code and the same name.
snippsat likes this post
Reply
#4
Ok. I get it.

function is called with 4 #do not issue return statement. n = 7

child function is called with 3 #Do not return n = 2 pause
child function is called with 2 # Do not return. n = 1 pause
child function is called with 1 # do not return. n = 0
(recursion rewinds)
# Now we issue the return statement with the last child and add it to parent until all functions have been called.
# Main function call returns n = 10

All calls to recursive function have to be completed before the left part of the statement can be executed the return + n can happen, which adds up all of the values already open in parent functions. Then, main return called with the sum of all, which is 10

All function calls have their own scope and place in memory. Nothing is overriden.

Right?



e
(Dec-03-2020, 05:38 PM)bowlofred Wrote:
(Dec-03-2020, 05:07 PM)muzikman Wrote: 1. Each recursive call simply returns the value of n to each child recursive call.

You don't return to a child, you pass an argument to a child. The child returns a value to its parent.

Each instance of the function call has its own copy of the variables, so nothing is "overwritten" here. One call has n=5, the child has n=4, but the variables are separate.

Quote:Basically the variable n will be overwritten by returning the sum of
n = n + get_recursive_sum(n - 1)
to each of the child calls until we get to zero. Recursion stops and the last value is returned to the initial caller which is the value of 10.

No. Each child returns only to its parent.

Quote:2. Starting with the first call n = 4, 4 and subsequent values are added then overwritten by return values.

Nothing is overwritten. more like this...
4 + get_recursive_sum(4 - 1) #pause
                    get_recursive_sum(3 - 1) #pause
                       get_recursive_sum(2 - 1) #pause
                         get_recursive_sum(1 - 1) #returns 0
                       unpause.  calculate 0+1 and return 1
                    unpause.  calculate 2 + 1 and return 3
                  unpause.  calculate 3 + 3 and return 6
               gets the 6 from the child and calculates 4 + 6 as 10.
The addition can't happen until it knows the answer from the child. So each instance will pause and wait for the child to finish and come back. Then the answers return in reverse order, always from one child to it's immediate parent.
Reply
#5
I think it's time to move on to the next topic in my course on Python. I can see how recursion can be slow with all of those functions in memory running at once. I can also see how it can be beneficial.

I started coding 23 years ago and I was taught, make your code easy to read and document it, even at the expensive of writing a few extra lines of code. I will stick to this, it has never failed me.

Thanks for all your help.
Reply
#6
Just alone for the way Thonny show recursion it's worth a download.
So it follow recursion just press F7 and a new window is created for each recursion with all step show.
It's not my my main editor,but has some cool features.
[Image: Yb9uy3.png]

muzikman Wrote:I can see how recursion can be slow with all of those functions in memory running at once
There are some trix for speeding things up a lot like write Memoization for the function.
There already stuff for this in standard library like @lru_cache.
So if make Fibonacci it will soon take a lot of time.
def fib(n):
   if n <= 1:
       return n
   else:
       return fib(n-1) + fib(n-2)

print(fib(38))
So this speed it up a lot.
from functools import lru_cache

@lru_cache()
def fib(n):
   if n <= 1:
       return n
   else:
       return fib(n-1) + fib(n-2)

print(fib(38))
If use Python 3.9 there even a faster way with just @cache
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  with open context inside of a recursive function billykid999 1 552 May-23-2023, 02:37 AM
Last Post: deanhystad
  Why recursive function consumes more of processing time than loops? M83Linux 9 4,131 May-20-2021, 01:52 PM
Last Post: DeaD_EyE
  Combine Two Recursive Functions To Create One Recursive Selection Sort Function Jeremy7 12 7,199 Jan-17-2021, 03:02 AM
Last Post: Jeremy7
  Don't Understand Recursive Function muzikman 9 3,576 Dec-03-2020, 05:10 PM
Last Post: muzikman
  list call problem in generator function using iteration and recursive calls postta 1 1,863 Oct-24-2020, 09:33 PM
Last Post: bowlofred
  Recursive function returns None, when True is expected akar 0 3,354 Sep-07-2020, 07:58 PM
Last Post: akar
  factorial using recursive function spalisetty06 12 3,953 Aug-25-2020, 03:16 PM
Last Post: spalisetty06
  Recursive Function sridhar 7 2,737 Jul-14-2020, 07:53 PM
Last Post: deanhystad
  Nested Recursive Function not Returning Etotheitau 2 2,218 May-09-2020, 06:09 PM
Last Post: Etotheitau
  Information "creeps up" in recursive function InigoMontoya 2 1,808 Sep-17-2019, 06:25 PM
Last Post: jefsummers

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020