4 Replies - 168 Views - Last Post: 09 February 2016 - 10:50 PM

#1 DerGiLLster  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-October 15

How to solve this recursion problem?

Posted 09 February 2016 - 04:18 PM

I have a recursive function called fun that process a list by repeatedly subdividing and operating on halves of the list by repeatedly subdividing and operating on halves of the list.

The base case is when the function is asked to operate on a function of size 1. It requires performing the step: fun(left) + fun(right). If each function call consumes 100 bytes of memory, how many bytes will be on the activation stack when the function is at it's peak memory consumption for a list of size 8?

I would imagine it being 800 bytes since, it calls upon each size being 100 bytes. Am I interpreting this question right or no? Is the relation between size and bytes off?

Is This A Good Question/Topic? 0
  • +

Replies To: How to solve this recursion problem?

#2 tlhIn`toq  Icon User is offline

  • Freelance developer
  • member icon

Reputation: 6160
  • View blog
  • Posts: 13,584
  • Joined: 02-June 10

Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:28 PM

Are you asking us to answer your homework question/problem for you?
Was This Post Helpful? 0
  • +
  • -

#3 DerGiLLster  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-October 15

Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:37 PM

No I;m asking if my answer, 800 bytes, is right. If not, what am I doing wrong?
Was This Post Helpful? 0
  • +
  • -

#4 tlhIn`toq  Icon User is offline

  • Freelance developer
  • member icon

Reputation: 6160
  • View blog
  • Posts: 13,584
  • Joined: 02-June 10

Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:46 PM

100 bytes per call
Each call cuts the list in half
The list size is 8
So how many times must the list be cut in half, then each half in half {repeat recursively}? That's the number of times the function is called. Times 100bytes per call.

Its not a straight 8*100bytes. You have to walk through the logical operation to see how many times the function is called.

If nothing else, just write a quick bit of code to walk through it and count the number of times the function is called.

This post has been edited by tlhIn`toq: 09 February 2016 - 04:56 PM

Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 4601
  • View blog
  • Posts: 14,993
  • Joined: 05-May 12

Re: How to solve this recursion problem?

Posted 09 February 2016 - 10:50 PM

Also, the question is not how much memory is used after processing the list.

The question is:

View PostDerGiLLster, on 09 February 2016 - 06:18 PM, said:

how many bytes will be on the activation stack when the function is at it's peak memory consumption for a list of size 8?


Spoiler

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1